CsitLabs
  • CSIT Labs
  • 1st Semester
    • Digital Logics
      • Lab 1
      • Lab 2
      • Lab 3
      • Lab 4
      • Lab 5
      • Lab6
    • IIT
    • Physics Lab Report Formet
  • 2nd Semester
    • Algorithms used in Discrete Structure class
    • Microprocessor
      • 8085 Microprocessor
        • Arithmetic and Logical Instruction Set
        • Branching Instruction Set
        • Data Transfer and Instruction Set
        • Multiply, Divide and Memory Block Operations
        • Rotate Instruction Set
        • Subroutine, Stack and BCD Conversion](Subroutine_Stack_BCD_Conversion
      • 8086 Microprocessor
        • Basic Arithmetic
        • Practice Programs for 8086 Microprocessor
        • String Processing
    • Object Oriented Programming using C++
      • File Access Pointers
      • Standard Exceptions in C++
    • Statistics-I
  • 3rd Semester
    • Computer Architecture
      • Practical labs
    • Computer Graphics
      • Practial
      • Simulation of Two Dimensional Transformation
      • Scan Conversion Algorithm
    • Data Structures and Algorithms
      • Array methods (Introduction)
      • Stack
      • Queue
      • Recursion
      • Linked List
      • Sorting Algorithms
      • Searching and Hashing Algorithms
      • Trees and Graphs
      • Lab practice
    • Numerical Method Labs
      • Lab practice
    • Statistics-II Labs
      • Confidence interval of mean assuming normal distribution
      • One Sample T test
      • Two Sample T test
      • Regression Analysis
      • Two Sample T test
      • Design_of_Experiment
        • CRD (Completely Randomized Design)
        • RBD (Randomized Block Design)
        • RBD (Randomized Block Design)
      • Non-parametric_test
        • Binomial Test
        • Cochran Q test
        • Kolmogorov-Smirnov one sample test
        • Run test
        • Friedman-F_test
          • Friedman F test
          • Friedman F test
        • Kruskal-Wallis-H_test
          • Kruskal Wallis H test
          • Kruskal Wallis H test
        • Mann-Whitney-U_test
          • Mann Whitney U test
          • Mann Whitney U test
        • Median_test
          • Median Test
          • Median Test
        • Wilcoxon-Matched-pair_signed_rank_test
          • Wilcoxon Matched pair signed rank test
          • Wilcoxon Matched pair signed rank test
  • 4th Semester
    • Artificial Intelligence
    • Computer Networks
      • Networking commands in CMD
    • DBMS Lab
    • Operating System
      • Linux Commands
    • Theory of Computation
      • Lab 1 (DFA)
      • Lab 2 (NFA)
  • 5th Semester
    • Cryptography
    • Design and Analysis of algorithms
    • Multimedia
      • Animation Creation with Blender
      • FL Studio - Simple Effect Creation
      • Macromedia FreeHand - Logo Creation
      • Audio Mixing
      • Adobe Photoshop - ID Card Creation
      • Video Editing with Adobe Premiere Pro
    • Simulation & Modeling
      • Lab 1: Random Number Generation
    • System Analysis and Design
    • Web Technology
      • Lab Assignment – I (HTML)
      • Lab Assignment – II (CSS)
      • Lab Assignment – III (JavaScript and XML)
      • Lab Assignment – IV (PHP)
      • Web Technology
        • php
          • Database connection using PHP and MySQL
          • Login form
          • Login form
  • 6th Semester
    • Compiler Design and Construction
    • NET Centric Computing
      • Class Codes
        • Authentication and Authorization in ASP.NET
        • C# Basics
      • Lab Codes
        • Practical 1
        • Practical 2
          • Number Operations Web App
          • User Registration Form
          • User Registration Console App
        • Practical 3
          • Authentication and Authorization (Claims, Roles and Policies)
          • Client side state management in ASP.NET
          • Entity Framework Core
          • Form Validation
            • React form validation
          • HTML Tag Helpers
          • MVC demonstration
          • Razor Syntax
          • Server Side State Management in ASP.NET
      • Self Projects
        • Do while programs
        • Role playing game battle challenge
        • Project overview
        • Authentication
          • wwwroot
            • lib
              • jquery-validation
                • The MIT License (MIT)
  • 7th Semester
    • Advanced Java Programming
      • Class Codes
        • Unit1-6&8
          • javafx-sdk-21.0.1
            • legal
              • javafx.graphics
                • Independent JPEG Group (IJG) JPEG v9e
                • Mesa 3-D Graphics Library v21.0.3
              • javafx.media
                • Microsoft DirectShow Samples v156905
                • GNU Glib v2.72.0
                • GStreamer v1.20.1
                • LibFFI v3.4.4
              • javafx.web
                • IBM International Components for Unicode (ICU4C) v73.1
                • xmlsoft.org: libxml2 v2.10.4
                • xmlsoft.org: libxslt v1.1.35
                • WebKit Open Source Project: WebKit v616.1
          • src
            • main
              • java
                • Unit 1: Programming in Java
                  • 2. Concepts and Topics
                • Unit 2: User Interface Components with Swing
                • Unit 3: Event Handling
                • Unit 4: Database Connectivity
                • Unit 5: Network Programming
                • Unit 6: GUI with JavaFX
        • Unit7
          • src
            • main
              • webapp
                • index
      • Lab Codes
        • Lab
          • src
            • main
              • java
                • Practical 1
                • Practical 2
                • Practical 3
                • Practical 4
                • Practical5
    • Data warehouse and Data mining
  • docs
    • Contributor Covenant Code of Conduct
Powered by GitBook
On this page
  • Programs
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Shell Sort
  • Merge Sort
  • Quick Sort
  • Heap Sort
  • References

Was this helpful?

  1. 3rd Semester
  2. Data Structures and Algorithms

Sorting Algorithms

PreviousLinked ListNextSearching and Hashing Algorithms

Last updated 8 months ago

Was this helpful?

Sorting is the process of arranging data into meaningful order so that you can analyze it more effectively.

Internal sorting: If the input data is such that it can be adjusted in the main memory at once, it is called internal sorting.

External sorting: If the input data is such that it cannot be adjusted in the memory entirely at once, it needs to be stored in a hard disk, floppy disk, or any other storage device.

Programs

  1. Comparison Sorting

  2. Divide and Conquer

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

  • Algorithm:

    1. Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1

    2. If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on

    3. Print the sorted array

       begin BubbleSort(arr)  
        for all array elements  
           if arr[i] > arr[i+1]  
              swap(arr[i], arr[i+1])  
           end if  
        end for     
        return arr     
     end BubbleSort  
  • Time Complexity: O(N2)

  • Auxiliary Space: O(1)

Insertion Sort

In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved.

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

  • Algorithm

    1. Iterate from arr[1] to arr[N] over the array.

    2. Compare the current element (key) to its predecessor.

    3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

  • Time Complexity: O(N2)

  • Auxiliary Space: O(1)

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.

  • The algorithm maintains two subarrays in a given array.

    • The subarray which already sorted.

    • The remaining subarray was unsorted.

    • In every iteration of the selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

   SELECTION SORT(arr, n)  

   Step 1: Repeat Steps 2 and 3 for i = 0 to n-1  
   Step 2: CALL SMALLEST(arr, i, n, pos)  
   Step 3: SWAP arr[i] with arr[pos]  
   [END OF LOOP]  
   Step 4: EXIT  

   SMALLEST (arr, i, n, pos)  
   Step 1: [INITIALIZE] SET SMALL = arr[i]  
   Step 2: [INITIALIZE] SET pos = i  
   Step 3: Repeat for j = i+1 to n  
   if (SMALL > arr[j])  
        SET SMALL = arr[j]  
   SET pos = j  
   [END OF if]  
   [END OF LOOP]  
   Step 4: RETURN pos  
  • Time Complexity: O(N2)

  • Auxiliary Space: O(1) => as the only extra memory used is for temporary variables while swapping two values in Array. The selection sort never makes more than O(N) swaps and can be useful when memory write is a costly operation.

Shell Sort

Shell sort is mainly a variation of Insertion Sort.The idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.

  • Algorithm:

    1. Start.

    2. Initialize the value of gap size. Example: h.

    3. Divide the list into smaller sub-part. Each must have equal intervals to h.

    4. Sort these sub-lists using insertion sort.

    5. Repeat this step 2 until the list is sorted.

    6. Print a sorted list.

    7. Stop.

        ShellSort(a, n) // 'a' is the given array, 'n' is the size of array  
        for (interval = n/2; interval > 0; interval /= 2)  
        for ( i = interval; i < n; i += 1)  
        temp = a[i];  
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)  
        a[j] = a[j - interval];   
        a[j] = temp;  
        End ShellSort      
  • Time Complexity: O(N^2)

  • Auxiliary Space: O(1)

Merge Sort

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

  • Algorithm:

    1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

    2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.


Step 1: start

Step 2: declare array and left, right, mid variable

Step 3: perform merge function.
    if left > right
        return
    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)
    merge(array, left, mid, right)

Step 4: Stop
  • Time Complexity: O(N*log(N))

  • Auxiliary Space: O(N)

Quick Sort

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

  • Always pick first element as pivot.

  • Always pick last element as pivot (implemented below)

  • Pick a random element as pivot.

  • Pick median as pivot.

   QUICKSORT (array A, start, end){  
      if (start < end){
         p = partition(A, start, end)
         QUICKSORT (A, start, p - 1)
         QUICKSORT (A, p + 1, end)    
      }   
   }  
  • Time Complexity: O(N^2)

  • Auxiliary Space: O(n*logn)

Heap Sort

Heap Sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

  • Algorithm:

    1. Build a max heap from the input data.

    2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

    3. Repeat above steps while size of heap is greater than 1.

     HeapSort(arr)  
     BuildMaxHeap(arr)  
     for i = length(arr) to 2  
        swap arr[1] with arr[i]  
        heap_size[arr] = heap_size[arr] ? 1  
        MaxHeapify(arr,1)  
     End  
  • Time Complexity: O(n log(n))

  • Auxiliary Space: O(1)

References

Bubble Sort
Insertion Sort
Selection Sort
Shell Sort
Merge Sort
Quick Sort
Heap Sort
GeeksforGeeks
Tutorials Point