Sorting

This chapter examines various sorting algorithms, including bubble sort, insertion sort, selection sort, quick sort, merge sort, heap sort, radix sort, and shell sort. It covers their algorithms, complexities, and comparisons.

Questions And Solutions

2078 Chaitra

Write an algorithm for quick sort. Sort the following numbers using quick sort: 30,25,70,19,48,28,21,44 and 120.

Solution:

quickSort(arr, low, high) if low < high pivot_idx = partition(arr, low, high) quickSort(arr, low, pivot_idx - 1) quickSort(arr, pivot_idx + 1, high)

partition(arr, low, high) pivot = arr[high] i = low - 1 for j = low to high - 1 if arr[j] < pivot i = i + 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high]) return i + 1

Initially: 30 25 70 19 48 28 21 44 120

Choose pivot 120, partition around it.

Pass 1: 30 25 70 19 48 28 21 44 120

Apply quickSort to subarray 30, 25, 70, 19, 48, 28, 21, 44.Choose pivot 44, partition around it.

Pass 2: 30 25 19 21 28 44 70 48

Apply quickSort to subarray 30, 25, 19, 21, 28.Choose pivot 28, partition around it.

Pass 3: 30 25 19 21 28

Apply quickSort to subarray 30, 25, 19, 21.Choose pivot 21, partition around it.

Pass 4: 19 21 25 30

Apply quickSort to subarray 25, 30.Choose pivot 30, partition around it.

Pass 5: 25 30

Apply quickSort to subarray 70, 48.Choose pivot 48, partition around it.

Pass 6: 48 70

Apply quickSort to subarray 70.

Final Sorted Array: 19, 21, 25, 28, 30, 44, 48, 70, 120

2074 Bhadra

Explain selection sort. Sort data sequence 40 90 20 -10 30 5 60 100 80 using selection sort method.

Answer:

Selection Sort is an unstable, in-place, comparison-based sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion and places it in its correct position. This process continues for n-1 passes to sort an array of n elements. In each iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

selectionSort(arr,n)

  1. for i = 0 to n-1
  2. min_idx = i;
  3. for j = i+1 to n-1
  4. if arr[j] < arr[min_idx]
  5. min_idx = j
  6. swap(arr[min_idx], arr[i])

More on Selection Sort

Intially: 40 90 20 -10 30 5 60 100 80

Find smallest in between arr[0] and arr[8] i.e. -10 ,swap -10 with the element at index 0-> 40.

Pass 1: -10 90 20 40 30 5 60 100 80

Find smallest in between arr[1] and arr[8] i.e. 5 ,swap 5 with the element at index 1-> 90.

Pass 2: -10 5 20 40 30 90 60 100 80

Find smallest in between arr[2] and arr[8] i.e. 20 ,since 20 is in correct position(index 2) so need to interchange.

Pass 3: -10 5 20 40 30 90 60 100 80

Find smallest in between arr[3] and arr[8] i.e. 30 ,swap 30 with the element at index 3-> 40.

Pass 4: -10 5 20 30 40 90 60 100 80

Find smallest in between arr[4] and arr[8] i.e. 40 ,since 40 is in correct position(index 4) so need to interchange.

Pass 5: -10 5 20 40 30 90 60 100 80

Find smallest in between arr[5] and arr[8] i.e. 60 ,swap 60 with the element at index 5-> 90.

Pass 6: -10 5 20 40 30 60 90 100 80

Find smallest in between arr[6] and arr[8] i.e. 80 ,swap 80 with the element at index 6-> 90.

Pass 7: -10 5 20 40 30 60 80 100 90

Find smallest in between arr[7] and arr[8] i.e. 90 ,swap 90 with the element at index 7-> 100.

Pass 8: -10 5 20 40 30 60 80 90 100

Finally it is in sorted order.

2066 Jestha

Define internal and external sorting. Write an algorithm for quick sort and trace your algorithm for a given sequence of data. 5, 43, 99, 20, 45, 7, 6, 63, 92, 4.

Solution:

Internal sorting is a type of sorting that takes place in the main memory (RAM) of a computer. It is used when the data to be sorted fits entirely within the available memory. Examples of internal sorting algorithms include quicksort, mergesort, and heapsort.

External sorting is a type of sorting that is used when the data to be sorted does not fit entirely in the main memory. It involves using external storage devices, such as hard drives or SSDs, to store and sort the data. External sorting algorithms are designed to minimize the number of disk accesses and efficiently handle large datasets. Examples of external sorting algorithms include external mergesort and polyphase mergesort.

quickSort(arr, low, high) if low < high pivot_idx = partition(arr, low, high) quickSort(arr, low, pivot_idx - 1) quickSort(arr, pivot_idx + 1, high)

partition(arr, low, high) pivot = arr[high] i = low - 1 for j = low to high - 1 if arr[j] < pivot i = i + 1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high]) return i + 1

Initially: 5 43 99 20 45 7 6 63 92 4

Choose pivot 4, partition around it.

Pass 1: 4 43 99 20 45 7 6 63 92 5

Apply quickSort to subarray 43, 99, 20, 45, 7, 6, 63, 92, 5.Choose pivot 5, partition around it.

Pass 2: 4 5 99 20 45 7 6 63 92 43

Apply quickSort to subarray 99, 20, 45, 7, 6, 63, 92, 43.Choose pivot 43, partition around it.

Pass 3: 4 5 20 7 6 43 45 92 63 99

Apply quickSort to subarray 20, 7, 6.Choose pivot 6, partition around it.

Pass 4: 4 5 6 7 20 43 45 92 63 99

Apply quickSort to subarray 7, 20.Choose pivot 20, partition around it.

Pass 5: 4 5 6 7 20 43 45 92 63 99

Apply quickSort to subarray 45, 92, 63, 99.Choose pivot 99, partition around it.

Pass 6: 4 5 6 7 20 43 45 92 63 99

Apply quickSort to subarray 45, 92, 63.Choose pivot 63, partition around it.

Pass 7: 4 5 6 7 20 43 45 63 92 99

Apply quickSort to subarray 45, 92.Choose pivot 92, partition around it.

Pass 8: 4 5 6 7 20 43 45 63 92 99

Final Sorted Array: 4, 5, 6, 7, 20, 43, 45, 63, 92, 99