Sorting an Array:

Sorting is the process of arranging the elements within a sequence into a particular order. For instance, a sequence of integers may be arranged in ascending order (from smallest to largest), while a sequence of words (strings) may be arranged in lexicographical (commonly called alphabetic) order.

Advertisment

There are several different methods to sort arrays, some performing much better than others. In this tutorial, we will discuss:

The basic goal of each method is to compare each array element to another array element and swap them if the higher value is less than the other.

Bubble Sort:

Bubble sort is one of the easiest sorting methods to understand. In Bubble sort, the values in the array are compared to each other, pair by pair, and swapped if they are not in back-to-back order. The lowest value eventually floats to the top of the array, akin to a bubble in a glass of soda.

Bubble sort steps through the array and compares pairs of numbers to determine whether they need to be swapped. Several passes might have to be made through the array before it is finally sorted (no more passes are needed).

Let's create a program to sort our numbers. In this program, we will input some numbers, and our program will return the sorted numbers in ascending order. We will create a sort()function to achieve this.

void sort(int *A, int n) {
    int temp; // Temporary variable
    for(int i = 0; i < n; i++) { // Loop for sorting
        for(int j = 0; j < n - 1; j++) { // Second loop for sorting
            if(A[j] > A[j + 1]) { // If n is greater than n + 1, then do swapping
                temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }
}

The above function sorts an array with two arguments: the array itself and the total number of items.

In the function, two loopsare used. The inner loop checks adjacent elements in the array, looking for out-of-order elements. When an out-of-order element pair is found, the two elements are exchanged. With each pass, the smallest element of those remaining moves into its proper location. The outer loop causes this process to repeat until the entire array has been sorted.

The if statementchecks the order of numbers, swapping them if necessary.

Now, let's analyze how it swaps numbers in arrays:

if (A[j] > A[j + 1]) {
    temp = A[j]; // Store the value of A[j] temporarily
    A[j] = A[j + 1]; // Replace A[j] with A[j+1]
    A[j + 1] = temp; // Replace A[j+1] with the temporary value
}

In simple terms, imagine three rooms: Room1, Room2, and Room3. If we want to interchange furniture between Room1 and Room2, we first need to temporarily move all furniture from Room2 to Room3. Then, we move the furniture from Room1 to Room2 since it's empty now. Finally, we move the furniture from Room3 to Room1.

Now, let's provide a complete example of Bubble sort. Users will enter some numbers, and our program will print these numbers in ascending order using the sort()function.

BUBBLE SORT - C++ Copy to Clipboard  
// Sorting Arrays: Bubble Sort

#include<iostream>
using namespace std;

void sort(int*, int); // Prototype for Sorting Function

int main() {
    int size = 10; // Size of Array
    int *ptr; // Pointer to Integer
    int num[size]; // Array of integers
    ptr = num; // Pointer points to the starting address of the array (num[0])

    if(ptr != NULL) { // Error checker if ptr didn't point to an array
        cout << "Enter 10 digits: " << endl;
        for(int i = 0; i < size; i++) { // Loop to get all numbers from the user
            cin >> ptr[i];
        }
    }
    sort(ptr, size); // Sorting function call

    cout << "Sorted Data: ";
    for(int i = 0; i < size; i++) { // Loop to print all sorted numbers
       cout << ptr[i] << " | ";
    }

    return 0;
}

// Sort Function Definition
void sort(int *A, int n) { // Arguments: array and total number
    int temp; // Temporary variable
    for(int i = 0; i < n; i++) { // Loop for sorting
        for(int j = 0; j < n - 1; j++) { // Second loop for sorting
            if(A[j] > A[j + 1]) { // If n is greater than n + 1, then do swapping
                temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            }
        }
    }
}

Quicksort:

Bubble sort is a simple way to sort data but is inefficient for larger datasets. The best general-purpose sorting algorithm is Quicksort. Quicksort, invented by C.A.R. Hoare, is the most efficient sorting algorithm currently available. Although it might be challenging for beginners to grasp, I'll do my best to explain quicksort thoroughly and simply.

The standard library <stdlib.h>contains a function called qsort(). Ensure to include stdlib in your program's header.

The qsort()function sorts an array of "n" elements whose first element is pointed to by Array. The size of each element is specified by size. The comparison function pointed to by compare is used to sort the content of the array in ascending order. qsort()calls the function with two arguments that point to the elements being compared.

int compare(const void* a, const void* b);

This function compares two numbers and returns:

  • Positive (+) if the first number is higher.
  • Negative (-) if the first number is lower.
  • Zero (0) if the numbers are the same.

Here's how you call qsort:

qsort(ArrayName, Size, DataSize, CompareFunctionCalling);
Advertisment

Qsort needs four arguments:

  • ArrayName:The name of the array.
  • Size:The size of the array.
  • dataSize:The size of the data (e.g., size of int, size of char, etc.).
  • CompareFunctionCalling:The compare function discussed earlier.

Now, let's provide a complete example of Quicksort. Users will enter 10 numbers, and our program will print these numbers in ascending order using the qsort()function.

QSORT - C++ Copy to Clipboard  
// Sorting function using qsort

#include<iostream>
#include<stdlib.h> // qsort function is defined here
using namespace std;

int compare(const void* a, const void* b) {
    int A = *((int*)a); // First pointer for dereference, and the other for casting
    int B = *((int*)b);

    return A - B; // Return + if ranked higher, - if ranked lower, and 0 if ranked the same
}

int main() {
    int A[10]; // Size of array
    cout << "Enter 10 digits: " << endl;
    for(int i = 0; i < 10; i++) { // Loop to get data from the user
        cin >> A[i];
    }
    qsort(A, 10, sizeof(int), compare); // qsort function call to sort array

    cout << "Sorted Data: ";
    for (int i = 0; i < 10; i++) { // Loop to display sorted array
        cout << A[i] << " | ";
    }

    return 0;
}
Advertisment
infobrother.com
AUTHOR

Sardar Omar

I did my hardest to present you with all of the information you need on this subject in a simple and understandable manner. However, if you have any difficulties understanding this concept or have any questions, please do not hesitate to ask. I'll try my best to meet your requirements.

Advertisment