INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56  (991 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB  #12  Sorting

Instructor: Bashir M. Ghandi

Objective:       Learn the two sorting methods –selection sort & quick sort

Apply the methods to a list of simple values and a list of records

 

What is Sorting?

·        Sorting is the re-arrangement of a collection of data according to some key-field.

·        It is a common activity in data management.  Even when a list is maintained in key order, there is often a need to re-arrange the list in a different order.

·        We shall consider only two of these sorting methods in this lab.

 

Selection Sort:

·        This includes the following steps:

1. Find the smallest (or largest) item in the list
2. Place this item at the beginning of the list
3. Repeat steps 1 and 2 starting at the beginning of the remaining list.

·        The following implements selection sort for a list of simple data items.  See Also LAB12_1.C.

 

void sel_sort1(int list[], int size)

{  int min_pos, start_pos;

   for(start_pos=0;  start_pos<size-1; start_pos++)

   {  min_pos=find_min_pos(list, size, start_pos);

      swap(&list[start_pos], &list[min_pos]);

   }

}

 

int find_min_pos(int list[], int size, int start_pos)

{  int i, min_pos=start_pos;

   for (i=start_pos+1; i<size; i++)

      if (list[i] < list[min_pos])

          min_pos = i;

  

   return min_pos;

}

 

void swap(int *a , int *b) {

   int temp = *a;

   *a =  *b;

   *b =  temp;

}

 

·        The following table shows a trace of how selection sort works:

Index	Original	Round1	Round3	Round 3
0	7	1	1	1
1	2	2	2	2
2	1	7	7	4
3	4	4	4	7

 

·        If a list contains structures, then the sorting is done based on a particular field called the key-field.  In  this case we only need to modify the find_min_pos to compare keys as follows:

      if (list[i].key < list[min_pos].key)

Quick Sort

·        Quick sort method uses divide-and-conquer approach to sort a list of items.

·        It first selects an element called the pivot and conceptually split the list into two sub-lists with respect to the pivot: the first sub-list consisting of all elements less than or equal to the pivot and the second consists of all elements that are greater or equal to the pivot.

·        These two sub-lists are then sorted using the same idea.  By the time the sub-lists reduce to single elements, the list would have been sorted.

·        The partitioning of a list is achieved by setting pointers left and right to the first and last values and allowing the pointers to move towards each other. 

·        The left pointer is allowed to increase until it reaches an element greater or equal to the pivot. 

·        The right pointer is allowed to decrease until it reaches an element less than or equal to the pivot. 

·        If the pointers do not cross, the elements they point to are swapped and the pointers move again.  This process continues until the pointers cross, at which stage the list would have been partitioned.

·        The algorithm is now applied on these sub-lists and the process continues until the list is sorted.

·        The following program implements this method.  See Also QUICKSOR.C

void QuickSort(int x[], int start, int end) {

     int left = start, right = end, pivot = x[(start + end)/2];

     partition(x, &left, &right, pivot);

     if(start < right)

         QuickSort(x, start, right);

     if(left < end)

         QuickSort(x, left, end);

}

 

void partition(int x[], int *left , int *right, int pivot) {

    do {

        while(x[*left] < pivot)

             (*left)++;

        while(x[*right] > pivot)

            (*right)--;

 

        if(*left < *right) {

            swap(&x[*left] , &x[*right]); //same swap as in selection sort

            (*left)++;

            (*right)--;

        }

        else if(*left == *right)

             (*left)++;

     } while(*left <= *right);

}

Programming Exercises:

1.   The program file LAB12_1.C  reads data from the file INTEGERS.DAT into a dynamic array.  It then sorts the data using selection sort and prints the result.  Download the program, study it and test run

 

2.   Modify the program in (1) above so that it sorts the records in the exams2.dat file based on the id_no field and print the result horizontally.  You should make use of the functions get_record, print_record etc. from previous labs.

 

3.   Modify Program 3 above so that it uses quick sort method.  Your program should be interactive with three options, as follows:

1.   Sort by ID Number

2.   Sort by Name

3.   Exit.