Software 1 - Sorting (5)

administrivia

Web Page - http://www.cs.tau.ac.il/~efif/courses/Software1_Spring_03

Sorting

• Binary insertion sort
• Bitonic sort
• Bubble sort
• Cocktail shaker sort
• Comparison countingl sort Distribution counting sort
• Heapsort
• Interval exchange sort
• List insertion sort
• List merge sort
• Median-of-three quicksort
• Merge exchange sort
• Merge insertion sort
• Multiple list insertion sort
• Natural merge sort
• Odd-even transposition sort
• P-operator sort
• Pratt sort
• Quicksort
• Radix exchange sort
• Radix insertion sort
• Radix list sort
• Samplesort
• Shellsort
• Straight insertion sort
• Tree insertion sort
• Tree selection sort
• Two-way insertion sort

Swap

void swap(int i, int j) { int temp; temp = buffer[i]; buffer[i] = buffer[j]; buffer[j] = temp; }

Sort

#include <stdio.h> #include <stdlib.h> #define BUFFER_SIZE 100 int buffer[BUFFER_SIZE]; int main() { int i, j, current; /* reading input */ for (i = 0; i < sizeof(buffer) && (scanf("%d", ¤t) == 1); ++i) buffer[i] = current; if (i >= sizeof(buffer)) return -1; insertion_sort(i); /* quick_sort(0, i-1); */ /* printing the sorted array */ for (j = 0; j < i; ++j) printf("%d ", buffer[j]); printf("\n"); return 0; }

Insertion sort

void insertion_sort(int size) { int j, k; for (j = 1; j < size; ++j) for (k = j; k > 0 && (buffer[k] < buffer[k-1]); --k) swap(k, k-1); }

Quicksort

void quick_sort(int left, int right) { int i, last; if (left >= right) return; swap(left, (left + right) / 2); last = left; for (i = left + 1; i <= right; ++i) if (buffer[i] < buffer[left]) swap(++last, i); swap(left, last); quick_sort(left, last - 1); quick_sort(last + 1, right); }