Sorting
- Simple:
– Bubble sort
– Selection sort
– Insertion sort
- Intermediate:
– Quick Sort
– Merge Sort
Bubble Short
- Compare two neighboring values.
- Compare and swap (if necessary)
- Also known as exchange sort
- Source Code of Bubble Sort:
Selection sort
Algorithm:
for(i=0; i<=N-2; i++){ /* N=number of data */
for(j=i; j<=N-1; j++){
Note the index of smallest value between A[j] s/d A[N-1],
Save it in variable k.
Swap A[i] with A[k].
}
}
Insertion sort
Algorithm:
for(i=1; i<n; i++) {
x = A[i], insert x to its suitable place between A[0] and A[i-1].
}
Quick sort
Algorithm:
void QuickSort(int left, int right)
{
if(left < right){
//arrange elements R[left],…,R[right] that
//producing new sequence:
R[left],…,R[J-1] < R[J] and R[J+1],…,R[right] > R[J].
QuickSort(left, J-1);
QuickSort(J+1, right);
}
}
Merge sort
- Merge Sort is a sorting algorithm based on the divide-and-conquer algorithm
- Divide-and-conquer is a general algorithm design paradigm
–Divide: divide the input data in two disjoint subsets
–Recur: solve the sub problems associated with subsets
–Conquer: combine the solutions for each subset into a solution