Sort an Array in Ascending Order in C++ (6 Ways)

In this article, we will discuss different ways to sort an array in C++.

How to sort an Array in C++?

Table Of Contents

Problem Description

Here we are given an array which needs to be sorted in ascending order.

Input

int arr[] = {0, 98, 761, 100, -982, -72};

Output

-982 -72 0 98 100 761

There are different ways to do it in C++. Let’s see all the techniques one by one.

Sort an Array in C++ using STL function sort()

The sort() function mainly accepts two arguments. First one is the starting address and second one is the last address of the array which need to be sorted. By default the sort() will sort the array in ascending order.

Example

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};

    // Get size of array
    size_t len = sizeof(arr) / sizeof(arr[0]);

    // Calling sort() function from STL
    // passing starting and ending address of array.
    sort(arr, arr + len);

    // Printing Output
    cout<<"The sorted array is: ";

    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The sorted array is: -982 -72 0 98 100 761

Also, there are commonly used 5 algorithms that can be used for sorting an array in Ascending order.

Sort an Array in C++ using Bubble Sort Approach

This is the simplest algorithm to sort an array in ascending order. In each step one element in the last of array is set in position.
bubble_sort() is the function in which bubble sort is implimented.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

//Bubble Sort Algorithm
void bubble_sort(int* arr, size_t len)
{
    int temp;
    for (int i = 0; i < len; i++)
        {
            for (int j = 0; j + 1 < len - i; j++)
            {

                // Swaping the elements if first one
                // is greater than second one.
                if (arr[j] > arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
}

// Driver Code
int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling bubble_sort function with given array
    bubble_sort(arr, len);

    // Printing Output
    cout<<"The sorted array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Output

The sorted array is: -982 -72 0 98 100 761

Sort an Array in C++ using Insertion Sort Approach

In this algorithm we will assume one subarray as sorted and go on adding elements to that array. Initially only single element of array is assumed to be sorted. insertion_sort() is the function in which insertion sort is implimented.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

void insertion_sort(int* arr, size_t len)
{
    int temp;
    // Assuming one element as sorted and inserting other elements to it
    for (int i = 1; i < len; i++)
    {
        temp = arr[i];
        // Finding the sorted position for selected element in sorted array and placing it into place.
        for (int j = i - 1; j >= 0; j--)
        {
            if (temp > arr[j])
            {
                arr[j + 1] = temp;
                break;
            }
            else if (temp <= arr[j])
            {
                arr[j + 1] = arr[j];
                if (j == 0)
                {
                    arr[j] = temp;
                }
            }
        }
    }
}

// Driver Code
int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling insertion_sort function with given array
    insertion_sort(arr, len);

    // Printing Output
    cout << "The sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The sorted array is: -982 -72 0 98 100 761

Sort an Array in C++ using Selection Sort Approach

In selection sort we will virtually divide the array into two parts viz sorted and unsorted. Sorted subarray will be in begining of array and we will select smallest element from the unsorted subarray and we will add it to sorted array.

Time Complexity: O(n^2)
Space Complexity: O(1)

Example

#include <iostream>

using namespace std;

void selection_sort(int* arr, int len)
{
    int min, temp;

    // Iterating for each element except first element.
    for (int i = 0; i < len - 1; i++)
    {
        min = arr[i];
        // Finding the minimum element from unsorted array and adding to sorted array.
        for (int j = i; j < len; j++)
        {
            if (min > arr[j])
            {
                min = arr[j];
                temp = j;
            }
        }
        arr[temp] = arr[i];
        arr[i] = min;
    }
}

// Driver Code
int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling selection_sort function with given array
    selection_sort(arr, len);

    // Printing Output
    cout << "The sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}

Output

The sorted array is: -982 -72 0 98 100 761

Sort an Array in C++ using Merge Sort Approach

Merge Sort works on Divide and Conquer algorithm technique. This algorithm consists of two main functions generally named as merge_sort() and merge(). The merge_sort() function will continously divide the array into smaller and smaller parts. The merge() function will merge all the subarrays according to ascending order, finally constructing the main array.

Time Complexity: O(nlog(n))
Space Complexity: O(n)

Example

#include <iostream>

using namespace std;

void merge_sort(int *arr, int start, int last);
void merge(int *arr, int start, int last);


// Driver Code
int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling the merge_sort function which recursively divides array into half
    merge_sort(arr, 0, len-1);

    // Printing Output
    cout << "The sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<<endl;
}


// This function divides array recursively.
void merge_sort(int *arr, int start, int last)
{
    if (start < last)
    {
        int mid = (start + last) / 2;
        merge_sort(arr, start, mid);  // Recurssion
        merge_sort(arr, mid + 1, last); // Recurssion
        merge(arr, start, last);
    }
}

// This function merges two sorted subarray into one in ascending order
void merge(int *arr, int start, int last)
{
    // Creating temporary array to store sorted array
    int temp[(last - start) + 1];
    int pos = 0;
    int i = start,j=(start + last)/2 + 1;

    // Filling the array in ascending order
    while(i<(start + last)/2 + 1 && j<=last)
    {
        if(arr[i] > arr[j])
        {
            temp[pos]=arr[j];
            j++;
        }
        else
        {
            temp[pos]=arr[i];
            i++;
        }
        pos++;
    }

    if(j>last)
    {
        while(i<((start + last)/2 + 1))
        {
            temp[pos]=arr[i];
            i++;
            pos++;
        }
    }
    else
    {
        while(j <= last)
        {
            temp[pos]=arr[j];
            j++;
            pos++;
        }
    }

    // Storing temp in array
    for(int i=0; i<(last - start + 1); i++)
    {
        arr[start + i] = temp[i];
    }
}

Output

The sorted array is: -982 -72 0 98 100 761

Sort an Array in C++ using Quick Sort Approach

This algorithm follows divide and conquer approach for sorting an array. Firstly in this algorithm we need to decide the pivot for quick sort to perform. It consists of a quick_sort() function which is called recursively.

Time Complexity: O(n^2)
Space Complexity: O(log(n))

Example

#include <iostream>

using namespace std;

void quick_sort(int *arr, int start, int last);

// Driver Code
int main()
{
    int arr[] = {0, 98, 761, 100, -982, -72};
    size_t len = sizeof(arr)/sizeof(arr[0]);

    // Calling the quick_sort function
    quick_sort(arr, 0, len-1);

    // Printing Output
    cout << "The sorted Array is: ";
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout<< endl;
}

void quick_sort(int *arr, int start, int last)
{
    if (start < last)
    {
        int i = start, temp, j = last, pivot = arr[start];

        // Placing the element from pivot to its sorted position.
        while (j >= i)
        {
            while (arr[i] <= pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i < j)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        temp = pivot;
        arr[start] = arr[j];
        arr[j] = temp;

        quick_sort(arr, j + 1, last);  // Recurssion
        quick_sort(arr, start, j - 1);  // Recurssion
    }
}

Output

The sorted array is: -982 -72 0 98 100 761

Summary

We have seen that how to sort array with help of STL function sort() and 5 different algorithms. Each algorithm has its own Time and Space complexity.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top