Scribd
Upload
5 views2 pages

GP - DSA - Sorting Notes

Sorting is the arrangement of elements in a specific order, which is crucial for many software applications. Various sorting algorithms exist, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, and Counting Sort, each classified by their space and time efficiency, as well as their stability and adaptability. Sorting algorithms can be categorized into in-place and out-place, stable and unstable, and adaptive and non-adaptive based on their characteristics and performance.

Uploaded by

nidhi.sharma.mtcs.2024
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

GP - DSA - Sorting Notes

Sorting is the arrangement of elements in a specific order, which is crucial for many software applications. Various sorting algorithms exist, including Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, and Counting Sort, each classified by their space and time efficiency, as well as their stability and adaptability. Sorting algorithms can be categorized into in-place and out-place, stable and unstable, and adaptive and non-adaptive based on their characteristics and performance.

Uploaded by

nidhi.sharma.mtcs.2024
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting

What is Sorting?

Sorting means an arrangement of elements in an ordered sequence either in


increasing(ascending) order or decreasing(descending) order. Sorting is very important and
many software and programs use this. The major difference is the amount of space and time
they consume while being performed in the program.

Different languages have their own in-built functions for sorting, which are basically hybrid
sorts that are a combination of different basic sorting algorithms. For example, C++ uses
introsort, which runs quicksort and switches to heapsort when the recursion gets too deep.
This way, you get the fast performance of quicksort in practice while guaranteeing a
worst-case time complexity of O(N*logN), where N is the number of elements.

We will be focusing mainly upon the following sorting algorithms:

● Selection Sort
● Bubble Sort
● Insertion Sort
● Merge Sort
● Quick Sort
● Counting Sort

The sorting algorithms are further classified on the following basis:

● In-place sorting and out-place sorting


○ In-place sorting: In-place sorting does not require any extra space except
the input space excluding the constant space which is used for variables or
iterators. It also doesn’t include the space used for stack in the recursive
algorithms. For Example, Bubble Sort, Selection Sort, Insertion Sort,
Quicksort, etc.
○ Out-place sorting: Out-place sorting requires extra space to sort the
elements. For Example, Merge Sort, Counting sort, etc.
● Stable and Unstable sorting

1
○ Stable sorting: A sorting algorithm when two objects with equal keys appear
in the same order in the sorted output as they appear in the unsorted input.
For Example, Insertion Sort, Merge Sort, Bubble Sort, Counting sort, etc.
○ Unstable sorting: A sorting algorithm is called unstable sorting if there are
two or more objects with equal keys which don’t appear in the same order
before and after sorting. For Example, Quick Sort, Heap Sort, Selection Sort,
etc.

Above is an example of stable sorting here number 26 is appearing two times at


positions 6 and 8 respectively in an unsorted array and their order of occurrence is
preserved in the sorted array as well and sorted array i.e. element 26 (blue) at position 6 in
unsorted array appears first in sorted array followed by another 26 (red) at position 8.

● Adaptive and Non-adaptive sorting


○ Adaptive sorting: When the order of occurrence of elements in an array
affects the time complexity of a sorting algorithm, then such an algorithm is
known as an adaptive sorting algorithm. For Example, Bubble sort, Insertion
Sort, Quick Sort, etc.
○ Non-adaptive sorting: When the order of occurrence of elements in an array
does not affect the time complexity of a sorting algorithm, then such an
algorithm is known as a non-adaptive sorting algorithm. For Example,
Selection Sort, Heap Sort, Merge Sort, etc.

You might also like