Quadratic sorting algorithm

Bubble sort:
Time complexity: O(n^2)
Can be used to detect whether an array is sorted.

Selection sort:
Time complexity: O(n^2)

Insertion sort:
Time complexity: O(n^2)
Very efficient on almost sorted array.
In practice, it is more efficient than other simple quadratic sorting algorithms such as selection sort and bubble sort.

Here are the source code for the sorting algorithms above.


void mySort::myBubbleSort(int *Q, int begin, int end){
bool isSorted=0;
int temp;
while(!isSorted){
isSorted=1;
for(int i=0; i<end; i++){
if(Q[i]>Q[i+1]){
temp=Q[i];
Q[i]=Q[i+1];
Q[i+1]=temp;
isSorted=0;
}
}
}
}

myMin mySort::myFindMin(int *Q, int begin, int end){
myMin minValue;
minValue.value=Q[begin];
minValue.pos=begin;
for(int i=begin; i<=end; i++){
if(Q[i]<minValue.value){
minValue.value=Q[i];
minValue.pos=i;
}
}
return minValue;
}
void mySort::mySelectionSort(int *Q, int begin, int end){
myMin minValue;
int temp;
for(int i=0; i<end;i++){
minValue=myFindMin(Q,i,end);
//cout<<"The minimum element is:"<<minValue.value<<" @ "<<minValue.pos<<endl;
temp=Q[i];
Q[i]=Q[minValue.pos];
Q[minValue.pos]=temp;
}
}

void mySort::myInsertionSort(int *Q, int begin, int end){
int temp;
int j;
for(int i=1; i<=end; i++){
temp=Q[i];
for(j=i-1; j>=0;j--){
if(Q[j]>temp)
 Q[j+1]=Q[j];
else{
break;
}
}
Q[j+1]=temp;
}
}

Heap and Heap sort

The following is the code of basic heap operations and heap sort.

//Here is the header file myHeap.h


#ifndef MYHEAP_H
#define MYHEAP_H
class myHeap{
int heapSize;
public:
int parent(int i){
return i/2;
}

int left(int i){
return 2*i;
}

int right(int i){
return 2*i+1;
}

void maxHeapify(int *A, int i);
void makeHeap(int *A, int size);
void myHeapSort(int *A, int size);
};

#endif

//Here is the source file myHeap.cpp


#include "myHeap.h"
void myHeap::maxHeapify(int *A, int i){
int l=left(i);
int r=right(i);
int temp=0;
int large;

if(l<=heapSize && A[l-1]>A[i-1]){
 large=l;
}
else
 large=i;

if(r<=heapSize && A[r-1]>A[large-1]){
 large=r;
}

if(large!=i){
temp=A[i-1];
A[i-1]=A[large-1];
A[large-1]=temp;
maxHeapify(A, large);
}

}

void myHeap::makeHeap(int *A, int size){
heapSize=size;
for(int i=heapSize/2; i>0; i--)
 maxHeapify(A,i);

}

void myHeap::myHeapSort(int *A, int size){
makeHeap(A,size);
for(int i=heapSize;i>1;i--){
int temp=A[0];
A[0]=A[i-1];
A[i-1]=temp;
heapSize--;
maxHeapify(A,1);
}
}

Things need to pay close attention to when designing the heap code:

1) The index of an array begins from zero. The index of a heap tree begins from one.

2) The use of "large" in maxHeapify is quite beautiful. You need to first compare A[l] with A[i] and assign the larger one to large. Then compare A[r] and A[large].