[go: up one dir, main page]
Scribd
Upload
61 views37 pages

Sorting

Sorting algorithms arrange elements in a list in a specific order. Internal sorting handles data that fits in memory while external sorting handles data too large for memory. Stable sorting maintains order of equal elements while unstable sorting may change their order. Bubble sort iterates through a list comparing and swapping adjacent elements. Selection sort finds the minimum element and places it at the front in each iteration. Merge sort divides the list in half recursively then merges the sorted halves. Quicksort uses partitioning to place elements into sorted order in each iteration. Heap sort uses a heap data structure to extract elements in sorted order. Insertion sort maintains a sorted sublist that it inserts elements into sequentially. Radix sort performs digit-by-digit sorting from least to

Uploaded by

Shikhar Ashish
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
61 views37 pages

Sorting

Sorting algorithms arrange elements in a list in a specific order. Internal sorting handles data that fits in memory while external sorting handles data too large for memory. Stable sorting maintains order of equal elements while unstable sorting may change their order. Bubble sort iterates through a list comparing and swapping adjacent elements. Selection sort finds the minimum element and places it at the front in each iteration. Merge sort divides the list in half recursively then merges the sorted halves. Quicksort uses partitioning to place elements into sorted order in each iteration. Heap sort uses a heap data structure to extract elements in sorted order. Insertion sort maintains a sorted sublist that it inserts elements into sequentially. Radix sort performs digit-by-digit sorting from least to

Uploaded by

Shikhar Ashish
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 37

Sorting

• Sorting is an algorithm that arranges the elements of a list in a certain order


[either ascending or descending].
• The output is a permutation or reordering of the input.
• Internal vs. External Sorting: When all data is placed in the main
memory or internal memory then sorting is called internal sorting. Example:
bubble sort. When all data that needs to be sorted cannot be placed in memory
at a time, the sorting is called external sorting. Example: merge sort.
• Stable vs. Unstable Sorting: When two same data appear in the same order in
sorted data without changing their position is called stable sort.
Example: merge sort, insertion sort. When two same data appear in
the different order in sorted data it is called unstable sort. Example: quick sort,
heap sort.
Bubble Sort

• Bubble sort is the simplest sorting algorithm.


• It works by iterating the input array from the first element to the last,
comparing each pair of elements and swapping them if needed.
• The algorithm gets its name from the way smaller elements “bubble”
to the top of the list.
Bubble Sort
void bubble(int a[], int n) 
 {  
   int i, j, temp;  
   for(i = 0; i < n; i++)    
    {    
      for(j = i+1; j < n; j++)    
        {     i j
            if(a[j] < a[i])    
            {    
                temp = a[i];    
                a[i] = a[j];    
                a[j] = temp;     
            }     
        }     
    }      Time complexity – O(
 }  
Selection Sort

• Selection algorithm sorts an array by repeatedly finding the minimum


element from unsorted part and putting it at the beginning.
void selection(int arr[], int n)  
{  
    int i, j, small;  
    for (i = 0; i < n-1; i++)    // One by one move boundary of unsorted subarray  
    {  
        small = i; //minimum element in unsorted array  
        for (j = i+1; j < n; j++)  
        {if (arr[j] < arr[small])  
             small = j;  
   }
    int temp = arr[small];  
    arr[small] = arr[i];  
    arr[i] = temp;  
    }   Time complexity – O(
}  
Merge Sort
• The Merge Sort algorithm is based on the Divide and
Conquer paradigm.
• In this algorithm, the array is initially divided into two equal halves
and then they are combined in a sorted manner.
• It is a recursive algorithm which continuously splits the array in half
until it cannot be further divided.
Merge Sort
inde 0 1 2 3 4 5 6 7
x
value split
22 18 12 - 58 7 31 42
4
22 18 12 -4 58 7 31 42
split split

22 18 12 -4 58 7 31 42
split split split split

22 18 12 -4 58 7 31 42
merge merge merge merge
18 22 -4 12 7 58 31 42
merge merge
-4 12 18 22 7 31 42 58
merge
-4 7 12 18 22 31 42 58
18 22 -4 12
i j

18 22 -4 12
i j

18 22 -4 12 i<= mid
j<=high
i j

-4 12 18 22
Quick Sort
• Quicksort is the widely used sorting algorithm that
makes n*logn comparisons in average case for sorting an array of n
elements.
• It is a faster and highly efficient sorting algorithm.
• This algorithm follows the divide and conquer approach.
• Divide and conquer is a technique of breaking down the algorithms
into subproblems, then solving the subproblems, and combining the
results back together to solve the original problem.
Quick Sort
Quick Sort
int partition (int a[], int start, int end)  
{  
    int pivot = a[end]; // pivot element  
/* function to implement quick sort */  
    int i = (start - 1);  
void quick(int a[], int start, int end)  
    for (int j = start; j <= end - 1; j++)  
{  
    {   // If current element is smaller than the pivot  
    if (start < end)  
        if (a[j] < pivot)  
    {  
        {           int p = partition(a, start, end); //p is the partitioning index  
            i++;          quick(a, start, p - 1);  
            int t = a[i];           quick(a, p + 1, end);  
            a[i] = a[j];       }  
            a[j] = t;   }  
        }    
    }  
    int t = a[i+1];  
    a[i+1] = a[end];  
    a[end] = t;  
    return (i + 1);  
}  
Heap
• A heap is a tree with some special properties. The basic requirement of a heap is
that the value of a node must be ≥ (or ≤) than the values of its children. This is
called heap property.

Which of these is a heap?


Heapify
Heap Sort
Heap Sort
HeapSort(arr)   MaxHeapify(arr,i)  
BuildMaxHeap(arr)   L = left(i)  
for i = length(arr) to 2   R = right(i)  
If arr[L] > arr[i]  
    swap arr[1] with arr[i]  
largest = L  
        heap_size[arr] = heap_size[arr] - 1   else  
        MaxHeapify(arr,1)   largest = i  
End   If arr[R] > arr[largest]  
largest = R  
BuildMaxHeap(arr)   If largest != i  
    heap_size(arr) = length(arr)   swap arr[i] with arr[largest]  
    for i = length(arr)/2 to 1   MaxHeapify(arr,largest)  
MaxHeapify(arr,i)   End   
End  
Insertion Sort
• In this algorithm, each iteration removes an element from the input data and
inserts it into the correct position in the list being sorted.
• Here, a sub-list is maintained which is always sorted.
• For example, the lower part of an array is maintained to be sorted.
• An element which is to be inserted in this sorted sub-list, has to find its
appropriate place and then it has to be inserted there. Hence the name, insertion
sort.
• The array is searched sequentially and unsorted items are moved and inserted into
the sorted sub-list (in the same array).
Working of Insertion Sort
• Consider an example: arr[] = {12, 11,13, 5, 6}
First pass:
12 11 13 5 6
11 12 13 5 6

Second pass:
11 12 13 5 6
Working of Insertion Sort
Third pass:
11 12 13 5 6
11 12 5 13 6
12 5 12 13 6
5 11 12 13 6
Working of Insertion Sort
Fourth Pass:
5 11 12 13 6
5 11 12 6 13
5 11 6 12 13
5 6 11 12 13
5 6 11 12 13
Working of Insertion Sort
void insertionSort(int arr[], int n)
{   int i, key, j;
    for (i = 1; i < n; i++) 
    {   key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) 
        { arr[j + 1] = arr[j];
             j = j - 1;
        }
        arr[j + 1] = key;
    }
}
Radix Sort
• In Radix sort, there is digit by digit sorting is performed that is started
from the least significant digit to the most significant digit.
Example:

Pass 1:
Example:

Pass 2:
Example:

Pass 3:
Time Complexity of Sorting algorithms
Algorithm Time Complexity
    Best Average Worst
Selection Sort Ω(n^2) θ(n^2) O(n^2)
Bubble Sort Ω(n) θ(n^2) O(n^2)
Insertion Sort Ω(n) θ(n^2) O(n^2)
Heap Sort Ω(n log(n)) θ(n log(n)) O(n log(n))
Quick Sort Ω(n log(n)) θ(n log(n)) O(n^2)
Merge Sort Ω(n log(n)) θ(n log(n)) O(n log(n))

You might also like