Data Structures - Arrays - Sorting

In this tutorial we will learn to sort elements of an Array data structure.

Table of Content

• Sorting
• Example

Sorting

Sorting is a process of arranging the elements either in ascending (increasing) or descending (decreasing) order. The elements that are sorted have some kind of linear relationship between them. For example, we can sort a list of interger values in ascending order as they are numbers. Similarly, we can sort boxes in descending order based on their volume as they all have volume.

There are different sorting algorithms available. Some of them are listed below.

• Bubble Sort
• Quick Sort
• Merge Sort

Time complexity depends on the sorting algorithm used. Since we are using Bubble sort so our time complexity will be O(n²). There are other more efficient sorting algorithm available. Feel free to read about them here.

Click here for sorting algorithms.

Example

In the following C++ example we are going to sort the elements of the given array using Bubble sort algorithm.

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int SIZE = 5;
int arr[SIZE];
int END = -1;

void freshInsertElements()
{
  // initialize random seed
  srand(time(NULL));

  cout << "Inserting " << SIZE << " elements in the array arr..." << endl;
  int i;
  for (i = 0; i < SIZE; i++)
  {
    arr[i] = rand() % 100 + 1; // random number between 1 to 100
  }
  END = SIZE - 1;
}

void print()
{
  cout << "Printing the content of array arr..." << endl;
  int i;
  for (i = 0; i <= END; i++)
  {
    cout << "arr[" << i << "] = " << arr[i] << endl;
  }
  cout << endl;
}

void sort()
{
  cout << "Sorting..." << endl;
  int k, j, temp;
  for (k = 1; k <= SIZE - 1; k++)
  {
    for (j = 0; j <= SIZE - k - 1; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main(void)
{
  freshInsertElements();
  print();

  sort();
  print();

  return 0;
}

Output

Inserting 5 elements in the array arr...
Printing the content of array arr...
arr[0] = 15
arr[1] = 35
arr[2] = 8
arr[3] = 30
arr[4] = 20

Sorting...
Printing the content of array arr...
arr[0] = 8
arr[1] = 15
arr[2] = 20
arr[3] = 30
arr[4] = 35

Watch Bubble Sort video.