Array Sorting - Practice Problems
Last Updated : 24 Sep, 2024
Sorting an array means arranging the elements of the array in a certain order. Generally sorting in an array is done
to arrange the elements in increasing or decreasing order.
Problem statement: Given an array of integers arr, the task is to sort the array in ascending order and return
it, without using any built-in functions.
Example:
Input: arr = [5, 2, 4, 3, 1]
Output: [1, 2, 3, 4, 5]
Input: arr = [1, 2, 2, 1, 3, 5, 4]
Output: [1, 1, 2, 2, 3, 4, 5]
Popular Sorting Algorithms:
1. Bubble Sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not suitable for large arrays as its average and worst-
case time complexity is quite high.
2. Selection Sort: Selection sort is another sorting technique in which we find the minimum element in every
iteration and place it in the array beginning from the first index. Thus, a selection sort also gets divided into a
sorted and unsorted subarray.
3. Insertion Sort: Insertion sort similarly to the way we sort playing cards in our hands. The array is virtually
split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct
position in the sorted part.
4. Merge Sort: It is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the
array is repeatedly divided into two equal halves and then they are combined in a sorted manner.
5. Quick Sort: This is a sorting algorithm based on the divide and conquer approach where an array is divided
into subarrays by selecting a pivot element (element selected from the array).
6. Heap Sort: Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is
similar to the selection sort where we first find the minimum element and place the minimum element at the
beginning. Repeat the same process for the remaining elements.
7. Counting Sort: Counting sort is a sorting technique based on keys between a specific range. It works by
counting the number of elements having distinct key values (kind of hashing). Then do some arithmetic to
calculate the position of each element in the output sequence.
To learn more about all other types of Sorting Algorithms, refer to the below articles:
Introduction to Sorting Techniques - Data Structure and Algorithm Tutorials
Sorting Algorithms
Comparison of Sorting Algorithms:
Complexity of Sorting Best Average Worst Memory Stable Method
Algorithms Case Case Case Used
Quick Sort N * logN N * logN N2 N No Partitioning
Merge Sort N * logN N * logN N * logN N Yes Merging
Heap Sort N * logN N * logN N * logN 1 No Selection
Insertion Sort N N2 N2 1 Yes Insertion
Selection Sort N2 N2 N2 1 No Selection
Bubble Sort N N2 N2 1 Yes Exchanging
Counting Sort N+K N+K N+K N+K Yes Hashing
Implementing of Sorting Algorithm:
Below is a simple implementation of Bubble Sort Algorithms to sort the Array:
C++ C Java Python C# JavaScript
1
#include <bits/stdc++.h>
2
using namespace std;
4
// Function to sort the array using Bubble Sort
5
void sortArray(vector<int>& arr){
6
int n = arr.size();
8
for (int i = 0; i < n - 1; i++) {
9
bool swapped = false;
10
11
// Last i elements are already in place
12
for (int j = 0; j < n - i - 1; j++) {
13
if (arr[j] > arr[j + 1]) {
14
swap(arr[j], arr[j + 1]);
15
Output
Sorted array:
11 12 22 25 34 64 90
Complexity Analysis to Sort an Array using Bubble Sort:
Time Complexity: O(N2)
Auxiliary Space: O(1)
Important Terminologies in Array Sorting:
Here we will see several algorithms used for array sorting. But before that let us see some important terminologies
related to sorting:
In-Place Sorting: In-place sorting means arranging the elements without using any extra space other than the
given array.
Stability of Sorting: A sorting algorithm is said to be stable if the relative order of the same valued elements is
preserved in the final sorted array i.e., the relative order of the same valued elements in the sorted array is the
same as in the original array.
