EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Sorting in C++ 

Home » Software Development » Software Development Tutorials » C ++ Programming Tutorial » Sorting in C++ 

Sorting in C++ 

Introduction on Sorting in C++

Having a collection of elements to order, sorting helps in arranging the elements in the record based on ordering relation. Consider a file record which contains a lot of information, to access a list from the record it is necessary to have a key field to point the current location of the element. For example, consider a list of names on the database, it could be sorted alphabetically. Sorting placed an important role in the field of Computers and technology.  Let us see more in this article.

What is the Sorting in C++?

Sorting is the basic concept used by the programmer or researcher to sort the inputs required. The order of complexity is given by 0(N*log(N)). Sorting an input makes easier in solving many problems like Searching, Maximum and Minimum element. Although a sorting arranges data in the sequence, the efficiency of the process is very important which is based on two criteria: – Time and memory required to perform sorting on the given data. Time is measured by counting the comparisons of keys used. There are many algorithms available to sort. In general, Sorting in C++ are distinguished into two types:

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

  1. Internal Sorting
  2. External Sorting

Syntax and Example

Syntax:

C++ uses sort () built-in function for their algorithms, to sort the containers like vectors, arrays.

Sort(array , array +size);

Examples:

#include<iostream>
using namespace std;
int main ()
{
int ins[12] = { 19,13,5,27,1,26,31,16,2,9,11,21};
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
{
cout <<ins[i]<<"\t";
}
for(int k=1; k<12; k++)
{
int t = ins[k];
int j= k-1;
while(j>=0 && t <= ins[j])
{
ins[j+1] = ins[j];
j = j-1;
}
ins[j+1] = t;
}
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
{
cout <<ins[i]<<"\t";
}
}

Output:

Sorting in C++

How does it Work?

To start with we will take Quick Sort, which is considered an important method among various sorting types. The basic sorting of an array takes a Quicksort approach. There are different ways to implement sorting, the aim of each of these techniques is the same as comparing two elements and swapping them with the temporary variable. In this article, we shall discuss the most important sorting used for implementation. Following are:

  1. Bubble Sort
  2. Insertion Sort
  3. Quick Sort
  4. Selection Sort

There are Merge Sort, radix sort, tape sorting which we may discuss later. First, we will go with Bubble sort.

Popular Course in this category
C++ Training (4 Courses, 5 Projects, 4 Quizzes)4 Online Courses | 5 Hands-on Projects | 37+ Hours | Verifiable Certificate of Completion | Lifetime Access | 4 Quizzes with Solutions
4.5 (4,890 ratings)
Course Price

View Course

Related Courses
Java Training (40 Courses, 29 Projects, 4 Quizzes)C Programming Training (3 Courses, 5 Project)

1. Bubble Sort

Bubble sort is one of the simplest sort methods we can use it for applications. In this technique, successive swaps are made through the records to be sorted. At each step, it compares the key to the data and exchanges the elements if not in the desired order. Sorting is done with the adjacent elements at the time only one element is placed in the sorted place after a swap.

Example: Let us consider an unsorted array A[]={ 6,2,4,7,1}

6 2 4 7 1
 A[0] A[1] A[2] A[3] A[4]

Step 1: Comparing A [0] > A [1], if condition is true swap the element (6>2) true, place 2 in A [0]. Similarly, all the steps take the same until the array becomes sorted.

Now the array is A [] = {2,6,4,7,1}

Step 2: 6 is compared with 4. As 6 is greater than 4. Therefore, 6 and 4 are swapped.

Now the array is A [] = {2,4,6,7,1}

Step 3: Element 6 is compared with 7. Since 6<2 and the elements are in ascending order, elements are not swapped.

The sorted array is A [] ={2,4,6,7,1}.

Continue the process until the array is sorted.

2. Insertion Sort

In this technique we start with the second data element by assuming the first element is already sorted and comparison is done with the second element and the step is continued with the other subsequent element. In an array of N elements, it is necessary to have N-1 passes to have a sorted element.

Consider an array A[] = { 8,3,6,1}

8 3 6 1

Step 1: The first element looks for the largest element in the array to swap. If it is larger it remains the same and gets moved on to the second element, here 8 is greater than all, no swap is made.

8 3 6 1

Step2: Swapping with the second element

3 8 6 1

Step3: Swapping with the third element

3 6 8 1

Step4: Swapping with the fourth element

1 3 6 8

3. Quick Sort

This technique follows the divide and conquer algorithm and considered to be very efficient as well as quicker for huge arrays. They are divided into three subsections: a left, a right and the middle. The middle element has a single value and it is named as the pivot. The mechanism goes like this, the element in the left segment should not have a key larger than the middle element and the no element in right has a key that is smaller than that of the middle element. Now let’s start with an illustration of the process of sorting. Quicksort uses a recursive concept while sorting sub-part. The array is divided into subpart, again left and right segments are partitioned by conquering. Here in this example considering the last element has pivot and the first element is assumed low. Consider an array element

 49 22 11 16 56 30

Taking the rightmost element has the pivot element = 30

16 22 11 30 56 49

The element greater than the pivot is placed towards left, smaller at the right.

16 22 11 56 49

The pointer is placed at the pivot and is partitioned around a pivot.

11 22 16 56 49

The subparts are sorted individually.

11 16 22  30 49 56

Finally, we got a Sorted Array.

4. Selection Sort

This technique is also called exchange sorting performs dual operation searching and sorting. The implementation takes straight selection sorting as defined below. Here, it is required to identify the smallest element present in the array and this element is sorted in the first ith position, Next, the second smallest element is identified, and it is sorted in the second position. The selection sort exits its loop when the unsorted subpart becomes empty. The time complexity is given as O(n2).

Consider the following array:

63 26 13 23 12

1. Finding the smallest element and place it at the beginning and it is swapped with the position.

12 26 13 23 63

2. The second element a [1] is identified compare with the minimum element and place it in the second position, similarly, the pass continues.

12 13 26 23 64

Final sorted output

12 13 23 26 64

Conclusion

To conclude, this article focussed on sorting concepts and their working mechanism. All these sorting techniques use parallel processing concepts. Sorting forms a core building block in structuring algorithms to solve the problems of data in the real world by sorting the set of values according to the requirements.

Recommended Articles

This is a guide to the Sorting in C++. Here we discuss the Introduction and Syntax with examples along with How does it work. You can also go through our other suggested articles to learn more–

  1. Sorting in Tableau
  2. Iterator in C++
  3. Array Functions in C
  4. Heap Sort in C
  5. How Sorting is Performed in PHP?
  6. Heap Sort in Python
  7. Iterator in Java
  8. Top 11 Features and Advantages of C++
  9. Iterator in Python | Benefits and Examples of Python
  10. Insertion Sort in Data Structure | How to Works?

C++ Training (4 Courses, 3 Projects, 4 Quizzes)

4 Online Courses

5 Hands-on Projects

37+ Hours

Verifiable Certificate of Completion

Lifetime Access

4 Quizzes with Solutions

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C plus plus Programming Tutorial
  • Sorting
    • Sorting in C++ 
    • Heap Sort in C++
    • C++ Vector Sort
    • Insertion Sort in C++
    • Selection Sort in C++
  • Basic
    • Introduction To C++
    • What is C++
    • Features of C++
    • Applications of C++
    • Best C++ Compiler
    • C++ Data Types
    • C++ Double
    • C++ unsigned int
    • User Defined Data Types in C++
    • Variables in C++
    • C++ Keywords
    • Pointers in C++
    • C++ Void Pointer
    • Function Pointer in C++
    • Iterator in C++
    • C++ Commands
    • Object in C++
    • C++ Literals
    • C++ Reference
    • C++ Undefined Reference
    • String in C++
    • C++ Programming Language (Basics)
    • C++ Identifiers
    • C++ Header Files
    • Type Casting in C++
    • C++ Formatter
  • Operators
    • C++ Operators
    • Arithmetic Operators in C++
    • Assignment Operators in C++
    • Bitwise Operators in C++
    • Relational Operators in C++
    • Boolean Operators in C++
    • Unary Operators in C++
    • C++ Operator[]
    • Operator Precedence in C++
    • C++ operator=()
  • Control Statements
    • Control Statement in C++
    • if else Statement in C++
    • Else If in C++
    • Nested if in C++
    • Continue Statement in C++
    • Break Statement in C++
    • Switch Statement in C++
    • goto Statement in C++
    • C++ Struct
    • Loops in C++
    • Do While Loop in C++
    • Nested Loop in C++
  • Functions
    • C++ String Functions
    • Math Functions in C++
    • Friend Function in C++
    • Recursive Function in C++
    • Virtual Functions in C++
    • strcat() in C++
    • swap() in C++
    • strcmp() in C++
    • ceil function in C++
    • C++ begin()
    • size() in C++
    • C++ test()
    • C++ any()
    • C++ Bitset
    • C++ find()
    • C++?Aggregation
    • C++?String append
    • C++ String Copy
    • C++ end()
    • C++ endl
    • C++ push_back
    • C++ shuffle()
    • malloc() in C++
    • C++ reserve()
    • C++ unique()
    • C++ sort()
    • C++ find_if()
    • Reflection in C++
    • C++ replace()
    • C++ search()
    • C++ Memset
    • C++ size_t
    • C++ Substring
    • C++ Max
    • C++ absolute value
    • C++ memcpy
    • C++ wchar_t
    • C++ free()
    • C++ sizeof()
    • C++ Move Semantics
  • Array
    • Arrays in C++
    • 2D Arrays in C++
    • 3D Arrays in C++
    • Multi-Dimensional Arrays in C++
    • C++ Array Functions
    • String Array in C++
    • C++ Length of Array
    • C++ arraylist
  • Constuctor and Destructor
    • Constructor and Destructor in C++
    • Constructor in C++
    • Destructor in C++
    • Copy Constructor in C++
    • Parameterized Constructor in C++
  • Overloading and overriding
    • Overloading and Overriding in C++
    • Overloading in C++
    • Overriding in C++
    • Function Overloading in C++
    • Function Overriding in C++
    • Method Overloading in C++
  • Inhertiance
    • Types of Inheritance in C++
    • Single Inheritance in C++
    • Multiple Inheritance in C++
    • Hierarchical Inheritance in C++
    • Multilevel Inheritance in C++
    • Hybrid Inheritance in C++
  • Advanced
    • C++ namespace
    • Encapsulation in C++
    • Access Modifiers in C++
    • Abstract Class in C++
    • C++ Class and Object
    • What is Template Class in C++?
    • C++ Algorithm
    • Data Structures and Algorithms C++
    • C++ Garbage Collection
    • Virtual Keyword in C++
    • Access Specifiers in C++
    • Storage Class in C++
    • Call by Value in C++
    • Multimap in C++
    • C++ Multiset
    • C++ Lambda Expressions
    • Stack in C++
    • C++ Static
    • C++ static_cast
    • Deque in C++
    • C++ Vector Functions
    • C++ 2D Vector
    • C++ List
    • C++ Mutable
    • Enum in C++
    • Abstraction in C++
    • Signal in C++
    • C++ Queue
    • Priority Queue in C++
    • Regular Expressions in C++
    • C++ Hash Table
    • File Handling in C++
    • C++ Stream
    • ifstream in C++
    • C++ ofstream
    • C++ fstream
    • C++ Read File
    • C++ iomanip
    • Macros in C++
    • Templates in C++
    • C++ setprecision
    • C++ Int to String
    • C++ thread( )
    • C++ Thread Pool
    • C++ thread_local
  • Programs
    • Patterns in C++
    • Star Patterns In c++
    • Swapping in C++
    • Reverse Number in C++
    • Palindrome Program in C++
    • Palindrome in C++
    • Factorial Program in C++
    • Fibonacci Series in C++
    • Square Root in C++
    • Random Number Generator in C++
    • Prime Number in C++
    • Leap Year Program in C++
    • Anagram in C++
    • Armstrong Number in C++
    • Reverse String in C++
    • Socket Programming in C++
    • Matrix Multiplication in C++
    • C++ using vs typedef
    • C++ vector vs list
    • C++ vector vs array
  • Interview question
    • C++ Interview Questions
    • Multithreading Interview Questions C++

Related Courses

C++ Training Course

Java Training Course

C Programming Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C++ Training (4 Courses, 3 Projects, 4 Quizzes) Learn More