# Chapter 12 : Sorting II

### Topics covered in this snack-sized chapter:

• Sorts integers by comparing individual digits sharing the same significant position.
• A positional notation is required.
• To sort an array of two-digit numbers, the algorithm makes two sorting passes through the array.
• In the first pass, the elements of the array are sorted by the least significant decimal digit.
• In the second pass, the elements of the array are sorted by the most significant decimal digit.
• The second pass is done in such a way that it does not destroy the effect of the first pass.

• #### Radix Sort Algorithm arrow_upward

 Step 1 Look at the rightmost digit. Step 2 Assign the full number to that digit’s index. Step 3 Look at the next digit to the   left from the current sorted array, if there is no digit, pad a 0. Step 4 REPEAT STEP 3 UNTIL all numbers have been sorted.

###### Example:

• Step 0
• Original, unsorted list

• Step 1
• Sorting by least significant digit (1st place) gives.

• Notice that we keep 802 before 2, because 802 occurred before 2 in the original list
• Similarly, for pairs 170 & 90 and 45 & 75.
• Step 2
• Sorting by next digit (10th place) gives.

• Step 3
• Sorting by most significant digit(100th place) gives sorted list.

###### Note:

• Each of the above steps requires just a single pass over the data.
• Each item can be placed in its correct bucket without having to be compared with other items.

• #### Quick Sort arrow_upward

• Quick sort is also known as "partition-exchange“ sort.
• Rearranges array into two parts:
• Left part ≤ pivot value
• Right part > pivot value
• Average case:
• O(n log n) Comparisons to sort n items.
• Worst case:
• O(n2 ) Comparisons to sort n items.

#### Quick Sort Algorithm arrow_upward

• Quick Sort employs a divide and conquer strategy to divide a list into two sub-lists.
• The algorithm is as follows:
• Pick an element, called a Pivot, from the list.
• Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
• After this partitioning, the pivot is in its final position.
• This is called the Partition Operation.
• Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

#### Heap Sort arrow_upward

• A Heap is a data structure.
• Heap sort is a sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a Heap.
• Heap Sort is an in-place sorting algorithm so it is memory efficient.

• ###### Complexity:

O(nlog(n)) for n items.

#### Heap Sort Algorithm arrow_upward

 Step1 Build Heap- O(n) Build a complete binary tree taking n items as input. Ensure the binary tree satisfies the Heap Order property. Step2 Perform n deleteMax operations- O(log(n)) Delete the maximum element in the heap – which is the root node, and place this element at the end of the sorted array.

#### Example of Heap Sort arrow_upward

• Given an array of 6 elements:
•     15, 19, 10, 7, 17, 16,

• Sort it in ascending order using heap sort.

• ###### Steps:

• Consider the values of the elements as priorities and build the heap tree.
• Start deleteMin operations, storing each deleted element at the end of the heap array.
• After performing step 2, the order of the elements will be opposite to the order in the heap tree.
• Hence, if we want the elements to be sorted in ascending order, we need to build the heap tree in descending order - the greatest element will have the highest priority.
• Note that we use only one array , treating its parts differently:
• When building the heap tree, part of the array will be considered as the heap, and the rest part - the original array.
• When sorting, part of the array will be the heap, and the rest part - the sorted array.
• This will be indicated by colors: white for the original array, blue for the heap and red for the sorted array.
• Here is the array: 15, 19, 10, 7, 17, 6

###### Building the heap tree:

• The array represented as a tree, complete but not ordered:
• Start with the rightmost node at height 1 - the node at position 3 = Size/2.
It has one greater child and has to be percolated down:
• After processing array[3] the situation is:
• Next comes array[2]. Its children are smaller, so no percolation is needed.
• The last node to be processed is array[1]. Its left child is the greater of the children.
• The item at array[1] has to be percolated down to the left, swapped with array[2].
• As a result the situation is:
• The children of array[2] are greater, and item 15 has to be moved down further, swapped with array[5].
• Now the tree is ordered, and the binary heap is built.
• Sorting - performing deleteMax operations:

##### Delete the top element 19.

1. Store 19 in a temporary place. A hole is created at the top.

2. Swap 19 with the last element of the heap.

• As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
•  Instead it becomes a cell from the sorted array.

3. Percolate down the hole.

4. Percolate once more (10 is less that 15, so it cannot be inserted in the previous hole).

• Now 10 can be inserted in the hole.
• 2. DeleteMax the top element 17:

1. Store 17 in a temporary place. A hole is created at the top.

2. Swap 17 with the last element of the heap.

• As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
• Instead it becomes a cell from the sorted array.

3. The element 10 is less than the children of the hole, and we percolate the hole down:

4. Insert 10 in the hole.

##### DeleteMax 16:

1. Store 16 in a temporary place. A hole is created at the top.

2. Swap 16 with the last element of the heap.

• As 7 will be adjusted in the heap, its cell will no longer be a part of the heap.
• Instead it becomes a cell from the sorted array.

3. Percolate the hole down (7 cannot be inserted there - it is less than the children of the hole).

4. Insert 7 in the hole.

##### DeleteMax the top element 15:

1. Store 15 in a temporary location. A hole is created.

2. Swap 15 with the last element of the heap.

• As 10 will be adjusted in the heap, its cell will no longer be a part of the heap.
• Instead it becomes a position from the sorted array.

3. Store 10 in the hole (10 is greater than the children of the hole).

##### DeleteMax the top element 10.

1. Remove 10 from the heap and store it into a temporary location.

2. Swap 10 with the last element of the heap.

• As 7 will be adjusted in the heap, its cell will no longer be a part of the heap.
•  Instead it becomes a cell from the sorted array.

3. Store 7 in the hole (as the only remaining element in the heap.

• 7 is the last element from the heap, so now the array is sorted.

#### Thank You from Kimavi arrow_upward

• Please email us at Admin@Kimavi.com and help us improve this tutorial.