Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Selection Sort

In each iteration of the selection sort algorithm, the smallest item from an unsorted list is chosen and placed at the top of the unsorted list.

Algorithm of Selection Sorting

In order to sort an array of n elements in increasing order, use the following commands:


selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort


How Selection Sort Works?

Assume we're attempting to organise the components ascending.

  • Consider the first element the smallest.
Quick Sort
  • Compare the first and second elements. If the next element is less than the minimum, it should be the minimum.   Compare the third element to the minimum. If the third element is lesser, assign the minimum value to it; otherwise, do nothing. The process continues until the final element is added.
Quick Sort
  • Minimum is moved to the front of the unsorted list after each iteration.
Quick Sort
  • Indexing begins with the first unsorted element in each iteration. Steps 1–3 are repeated until all of the elements are in their proper places.
Quick Sort
Quick Sort
Quick Sort
Quick Sort

Code for Selection Sort in C

// Selection sort in C


#include <stdio.h>


// function to swap the the position of two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}


void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {


      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }


    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}


// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}


// driver code
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("Sorted array in Acsending Order:\n");
  printArray(data, size);
}


The following output should be generated by this programme:

Output


Array Sorted in Ascending Order:
-12 -9 0 17 46

Complexity for Selection Sort

Time Complexity
Best CaseO(n2)
Worst CaseO(n2)
AverageO(n2)
Space ComplexityO(1)
StabilityNo

Detail-oriented complexity

The nearby components are compared in Selection Sort.

CycleNumber of comparisons
1st( n-1 )
2nd( n-2 )
3rd( n-3 )
Last1

As a result, the number of iterations is:

( n-1 ) + ( n-2 ) + ( n-3 ) + ..... + 1 = n ( n-1 ) / 2

That almost equals n2

As a result, Complexity: O (n2)

Also, as we can see from the code, Selection sort necessitates two loops. As a result, the complexity is n*n = n2.

Complexities of Time

  • Complexity in the worst-case scenario: O (n2)
    • The worst case scenario happens if we wish to sort in ascending order but the array is in descending order.
  • Complexity in the Best-Case Scenario: O (n)
    • When the array has already been sorted, the outer loop repeats n times, but the inner loop does not. As a result, there are only n possible comparisons. As a result, complexity follows a linear pattern.
  • Case Complexity on the Average: O (n2)
    • When the items of an array are jumbled together, this happens (neither ascending nor descending).

The selection sort's time complexity is the same in all cases. At each step, you must identify the bare minimum and place it in the appropriate location. The minimum element is unknown until the array's end has not been reached.

Complexity of Space

  • Because an additional variable is utilised for swapping, the space complexity is O(1).

Applications for Selection Sorting

When using the selection sort,

  • Sorting a small list is considered necessary.
  • The cost of swapping is irrelevant.
  • It is necessary to check all of the elements.
  • In flash memory, the cost of writing to memory matters (number of writes/swaps is O(n) versus O(n2) for bubble sort).



ADVERTISEMENT
ADVERTISEMENT