Software 1 - Sorting (8)

administrivia

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

Swap

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

Sort

• mysort.c
• A simple main()

  #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)/sizeof(int) && (scanf("%d", ¤t) == 1); ++i) buffer[i] = current; if (i == 0) return; 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); }

A Thief with a key is still a thief

• Don't reference freed memory

  while (ptr != NULL) { free(ptr); ptr = ptr->next; }