some sort algorithms
October 9, 2014
In order to know whether a sort algorithm is stable, we need to know how it works.
SelectionSort
/*
* =====================================================================================
* Filename : SelectionSort.cpp
* Description : SelectionSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
const int N = 8;
int a[8] = { 7, 6, 3, 2, 1, 4, 5, 8 };
cout << "original array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
int min_index;
for ( int i = 0; i < N; ++i ) {
min_index = i;
for ( int j = i + 1; j < N; ++j ) {
if ( a[j] < a[min_index] ) {
min_index = j;
}
}
swap(a[i], a[min_index]);
}
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Is it stable? No.
* for example:
* 5 4 4 3 2 1
*
* first loop, we get:
* 1 4 4 3 2 5
*
* second loop, we get:
* 1 2 4 3 4 5
*
* In the second loop, the first 4 is placed after the second 4
* so select sort is not stable!
*
* Got it!
*/
InsertSort
/*
* =====================================================================================
* Filename : InsertSort.cpp
* Description : InsertSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
const int N = 8;
int a[8] = { 7, 6, 3, 2, 1, 4, 5, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
for ( int i = 1; i < N; ++i ) {
for ( int j = i; j > 0; --j ) {
if ( a[j] < a[j-1] ) {
swap(a[j], a[j-1]);
}
else {
break;
}
}
}
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is stable. ;-)
* Because we never exchange two element with the same value.
*/
ShellSort
/*
* =====================================================================================
* Filename : ShellSort.cpp
* Description : ShellSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
const int N = 8;
int a[8] = { 7, 6, 3, 2, 1, 4, 5, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
int h = 1;
while ( h < N / 3 ) {
h = h * 3 + 1;
}
while ( h >= 1 ) {
for ( int i = h; i < N; ++i ) {
for ( int j = i; j >= h; j -= h ) {
if ( a[j] < a[j-h] ) {
swap(a[j], a[j-h]);
}
else {
break;
}
}
}
h /= 3;
}
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is unstable. ;-)
*/
QuickSort
/*
* =====================================================================================
* Filename : QuickSort.cpp
* Description : QuickSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
/* Name: QuickSort
* Description: quick sort function
*/
void
QuickSort ( int low, int high, int a[] )
{
if (low >= high) return;
int i = low, j = high, tmp = a[low];
while ( true ) {
while ( a[j] >= tmp && j > i) --j;
while ( a[i] <= tmp && i < j ) ++i;
if (i == j) break;
swap(a[i], a[j]);
}
swap(a[i], a[low]);
QuickSort(low, i - 1, a);
QuickSort(i + 1, high, a);
return ;
} /* ----- end of function QuickSort ----- */
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
const int N = 8;
int a[8] = { 7, 6, 3, 2, 1, 4, 5, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
QuickSort(0, N - 1, a);
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is unstable. ;-)
*/
QuickSort-3partition
/*
* =====================================================================================
* Filename : QuickSort-3partition.cpp
* Description : QuickSort3Partition
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
/* Name: QuickSort
* Description: quick sort function
*/
void
QuickSort ( int low, int high, int a[] )
{
/*
* a[low, lt - 1] < tmp
* a[lt, i - 1] == tmp
* a[i, gt] unknown
* a[gt + 1, high] > tmp
*/
if (low >= high) return;
int i = low, lt = low, gt = high, tmp = a[low];
while ( i <= gt ) {
if (a[i] == tmp) ++i;
else if (a[i] < tmp) {
swap(a[lt], a[i]);
++lt;
}
else {
swap(a[gt], a[i]);
--gt;
}
}
QuickSort(low, lt - 1, a);
QuickSort(gt + 1, high, a);
return ;
} /* ----- end of function QuickSort ----- */
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
// const int N = 8;
// int a[8] = { 7, 6, 3, 2, 1, 4, 5, 8 };
const int N = 10;
int a[10] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
QuickSort(0, N - 1, a);
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is not stable. ;-)
* notice the case a[i] < tmp
*/
MergeSort
/*
* =====================================================================================
* Filename : MergeSort.cpp
* Description : MergeSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 8;
/* Name: MergeSort
* Description: MergeSort function
*/
void
MergeSort ( int low, int high, int a[] )
{
if ( low >= high ) return;
int mid = low + ((high - low) >> 1);
MergeSort(low, mid, a);
MergeSort(mid + 1, high, a);
// Merge
int a_new[N], i, j, k;
for ( i = low; i <= high; ++i ) {
a_new[i] = a[i];
}
i = low;
j = mid + 1;
for ( k = low; k <= high; ++k ) {
if ( i > mid ) {
a[k] = a_new[j++];
}
else if ( j > high ) {
a[k] = a_new[i++];
}
else if (a_new[j] < a_new[i]) {
a[k] = a_new[j++];
}
else {
a[k] = a_new[i++];
}
}
return ;
} /* ----- end of function MergeSort ----- */
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
int a[N] = { 7, 6, 3, 2, 1, 4, 5, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
MergeSort(0, N - 1, a);
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 0; i < N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is stable. ;-)
*/
HeapSort
/*
* =====================================================================================
* Filename : HeapSort.cpp
* Description : HeapSort
* Version : 0.1
* Created : 10/04/14 14:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <bits/stdc++.h>
using namespace std;
int N = 8;
/* Name: sink
* Description: sink one value down the heap
*/
void
sink ( int i, int a[] )
{
while ( i * 2 <= N ) {
int goal = 2 * i;
if ( 2 * i + 1 <= N && a[2*i+1] > a[2*i] ) { /* I have written a[2*i+1] > a[i] !!! fuck*/
goal = 2 * i + 1;
}
if ( a[i] < a[goal] ) {
swap(a[i], a[goal]);
}
else break;
i = goal;
}
return ;
} /* ----- end of function sink ----- */
/* NAME: HEAPSORT
* DESCRIPTION: HEAP SORT FUNCTION
*/
void
HeapSort ( int a[] )
{
for ( int i = N >> 1; i >= 1; --i ) {
sink(i, a);
}
for ( int i = 1; i < 8; ++i ) {
swap(a[1], a[N]);
--N;
sink(1, a);
}
return ;
} /* ----- end of function HeapSort ----- */
int
main ( int argc, char *argv[] )
{
// 1, 2, 3, 4, 5, 6, 7, 8
int a[9] = { 0, 7, 6, 3, 2, 1, 4, 5, 8 };
//print initial array
cout << "original array:" << endl;
for ( int i = 1; i <= N; ++i ) {
cout << a[i] << " ";
}
cout << endl;
HeapSort(a);
//output
cout << "\n\nsorted array:" << endl;
for ( int i = 1; i <= 8; ++i ) {
cout << a[i] << " ";
}
cout << endl;
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
/*
* Obviously, it is unstable. ;-)
*/