Basic sorting algorithms in cpp
//insertion sort
void insertionSort(int list[], const int listSize)
{
int i, j, key;
for (i = 1; i < listSize; i++)
{
key = list[i];
for (j = i-1; j >= 0 && list[j] > key; j--)
list[j + 1] = list[j];
list[j+1] = key;
}
}
//selection sort
void selectionSort(int list[], const int listSize)
{
int i, j, least, tmp;
for (i = 0; i < listSize-1; i++)
{
least = i;
for (j = i + 1; j < listSize; j++)
if (least > list[j]) least = j;
SWAP(list[least], list[i], tmp);
}
}
//bubble sort
void bubblleSort(int list[], const int listSize)
{
int i,j, tmp;
for(j = listSize-1; j>0; j--)
for (i = 0; i < j; i++)
if (list[i] > list[i + 1])
SWAP(list[i], list[i + 1], tmp);
}
// shell sort
void incInsertionSort(int list[], const int first, const int last, const int gap)
{
int i, j, key;
for (i = first + gap; i <= last; i += gap)
{
key = list[i];
for (j = i - gap; j >= first && list[j]>key; j -= gap) // like insertionSort
list[j + gap] = list[j];
list[j + gap] = key;
}
}
void shellSort(int list[], const int n)
{
int i, gap;
for (gap = n / 2; gap>0; gap /= 2)
{
if ((gap % 2) == 0) gap++;
for (i = 0; i<gap; i++)
incInsertionSort(list, i, n - 1, gap);
}
}
// quick sort
int partition(int list[], const int left, const int right)
{
int pivot, tmp;
int low, high;
low = left-1;
high = right;
pivot = list[right];
do
{
do
low++;
while (low <= right && list[low] < pivot);
do
high--;
while (high >= left && list[high]>pivot);
if (low < high)
SWAP(list[low], list[high], tmp);
} while (low < high);
SWAP(list[right], list[low], tmp);
return low;
}
void quickSort(int list[], const int left, const int right)
{
int q;
if (left < right)
{
q = partition(list, left, right);
quickSort(list, left, q - 1);
quickSort(list, q + 1, right);
}
}
// merge sort
int sorted[MAX_SIZE]; ////
static void merge(int list[], const int left, const int mid, const int right)
{
int i, j, k, l;
i = left; j = mid + 1; k = left;
while (i <= mid && j <= right)
{
if (list[i] <= list[j]) sorted[k++] = list[i++];
else sorted[k++] = list[j++];
}
if (i>mid)
for (l = j; l <= right; l++)
sorted[k++] = list[l];
else
for (l = i; l <= mid; l++)
sorted[k++] = list[l];
for (l = left; l <= right; l++)
list[l] = sorted[l];
}
void mergeSort(int list[], const int left, const int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
mergeSort(list, left, mid);
mergeSort(list, mid + 1, right);
merge(list, left, mid, right); // merge finally
}
}
| cs |
댓글 없음:
댓글 쓰기