Sorting Algorithms Overview

Sorting

• Sorting refers to arranging data in a specific format, typically numerical or alphabetical order.
• Sorting algorithms specify the methods to arrange data.
• Sorting enhances data searching efficiency and makes data presentation more readable.

Real-Life Sorting Scenarios

• Telephone directories store phone numbers alphabetically to facilitate name-based searches.
• Dictionaries organize words alphabetically for quick word lookup.

In-Place vs. Not-In-Place Sorting

• In-place sorting algorithms do not require extra space for processing, making changes directly within the input data.
• Examples include bubble sort, where data is sorted within the existing array.

Stable vs. Not Stable Sorting

• Stable sorting algorithms preserve the original order of identical elements in the sorted output.
• Unstable sorting algorithms may alter the order of elements with the same value during sorting.

Adaptive vs. Non-Adaptive Sorting

• Adaptive sorting algorithms exploit already sorted elements in the input to optimize sorting performance.
• Non-adaptive sorting algorithms treat all elements equally, regardless of pre-existing order, potentially re-sorting already sorted portions.

Increasing Order

• A sequence is in increasing order if each element is greater than the previous one.
• Example: 1, 3, 4, 6, 8, 9.

Decreasing Order

• A sequence is in decreasing order if each element is less than the previous one.
• Example: 9, 8, 6, 4, 3, 1.

Non-Increasing Order

• A sequence is in non-increasing order if each element is less than or equal to the previous one.
• Example: 9, 8, 6, 3, 3, 1.

Non-Decreasing Order

• A sequence is in non-decreasing order if each element is greater than or equal to the previous one.
• Example: 1, 3, 3, 6, 8, 9.

Bubble Sort

• Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
• The smallest element "bubbles" up to its correct position with each iteration.

Insertion Sort

• Insertion sort iteratively inserts elements into their correct positions within an already sorted sub-list.
• It functions similarly to how a person might sort playing cards.

Selection Sort

• Selection sort divides the input array into two parts: a sorted sub-array and an unsorted sub-array.
• It repeatedly finds the smallest element in the unsorted sub-array and swaps it with the first element of the unsorted sub-array.