Sorting Array in cpp

 

Sorting Arrays

Sorting is a process of arranging the values of array in a particular order. An array can be sorted in two orders:

Ascending Sort

In ascending order, the smallest value is stored in the first element of array; second smallest value is stored in the second element and so on. The largest value is stored in the last element. Following figure shows an array sorted in ascending order.

Sorted Array in Ascending order

Descending Sort

In descending order, the largest value is stored in first element of array, second largest value is stored in second element and so on. The smallest value is stored in the last element. 

The following figure shows an array sorted in descending order.

Sorted Array in Descending order

Selection Sort

Selection sort is a technique that sorts an array. It selects an element in the array and moves it to its proper position. Selection sort works as follows:

• Find minimum value in the list.

• Swap it with the value in the first position.

• Sort the remainder of the list excluding the first value.

Working of Selection Sort

Set the first element as minimum.

Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as minimum.

Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element.

After each iteration, minimum is placed in the front of the unsorted list.

swap the first with minimum

For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

The first iteration

The Second iteration

The third iteration

The fourth iteration

Selection Sort Algorithm

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

Selection Sort Code

// Selection sort in C++

#include <iostream>

using namespace std;

// function to swap the the position of two elements

void swap(int *a, int *b) {

  int temp = *a;

  *a = *b;

  *b = temp;

}

// function to print an array

void printArray(int array[], int size) {

  for (int i = 0; i < size; i++) {

    cout << array[i] << " ";

  }

  cout << endl;

}

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]);

  }

}

// driver code

int main() {

  int data[] = {20, 12, 10, 15, 2};

  int size = sizeof(data) / sizeof(data[0]);

  selectionSort(data, size);

  cout << "Sorted array in Acsending Order:\n";

  printArray(data, size);

}

Time Complexity

Best         O(n2)

Worst O(n2)

Average O(n2)