Scribd
Upload
10 views17 pages

Sorting

Sorting is the arrangement of data in a preferred order, which enhances search efficiency, exemplified by dictionaries and phone books. There are stable sorts that maintain the order of equal elements, like Bubble and Merge Sort, and unstable sorts that do not, like Quick and Heap Sort. Various sorting algorithms have different time complexities, with Bubble and Selection Sort having O(n^2) in the worst case, while Merge and Quick Sort can achieve O(n log n).

Uploaded by

patil.vikas6306
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
10 views17 pages

Sorting

Sorting is the arrangement of data in a preferred order, which enhances search efficiency, exemplified by dictionaries and phone books. There are stable sorts that maintain the order of equal elements, like Bubble and Merge Sort, and unstable sorts that do not, like Quick and Heap Sort. Various sorting algorithms have different time complexities, with Bubble and Selection Sort having O(n^2) in the worst case, while Merge and Quick Sort can achieve O(n log n).

Uploaded by

patil.vikas6306
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

The arrangement of data in a preferred order is called sorting in the data structure. By sorting
data, it is easier to search through it quickly and easily.
The simplest example of sorting is a dictionary.
Before the era of the Internet, when you wanted to look up a word in a dictionary, you would
do so in alphabetical order. This made it easy.
Sorting greatly improves the efficiency of searching.
If we were to open a phone book, and find that the names were not presented in any logical
order, it would take an incredibly long time to look up someone’s phone number the same panic
an engineer will go through if their data is not sorted and structured.
Stable and Unstable Sort

Stable sorting - Data is sorted in a way that preserves the original order of elements having
equal keys. This means that if two elements have the same key, the one that appeared earlier in
the input will also appear earlier in the sorted output. E.g - Bubble Sort, Insertion Sort, Merge
Sort
Unstable sorting – Data is sorted so that the order of elements with equal keys is not preserved
after sorting. E.g -Quick Sort, Heap Sort, and Selection Sort
Bubble Sort
Given an array of size:

 The first iteration performs (n-1) comparisons.

 The second iteration performs (n-2) comparisons.

 In this way, the total number of comparison will be:


Case Time Complexity

Best Case O(n2) / O(n)

Worst Case O(n2)


Insertion Sort
Time Complexity of Insertion Sort

Given an array of size:


 The first iteration performs 1 comparison.

 The second iteration performs 2 comparisons an so on ………up to (n-1) comparisons

 In this way, the total number of comparison will be:

Case Time Complexity


Best Case O(n)

Worst Case O(n2)


Time Complexity of Selection Sort
Given an array of size:

 The first iteration performs (n-1) comparisons.

 The second iteration performs (n-2) comparisons.


Case Time Complexity
 In this way, the total number of comparison will be:
Best Case O(n2)

Worst Case O(n2)


Merge Sort
Case Time Complexity

Best Case O(n logn)

Worst Case O(n logn)


Quick Sort
Case Time Complexity

Best Case O(n logn)

Worst Case O(n2)

1st small

1st small

1st large

You might also like