Scribd
Upload
23 views24 pages

Sorting

The document provides an overview of sorting algorithms, including definitions and classifications such as internal and external sorting. It details specific algorithms like Merge Sort, Insertion Sort, and Shell Sort, explaining their mechanisms and implementations. Additionally, it includes links for further resources on sorting algorithms.

Uploaded by

advika.sagar
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
23 views24 pages

Sorting

The document provides an overview of sorting algorithms, including definitions and classifications such as internal and external sorting. It details specific algorithms like Merge Sort, Insertion Sort, and Shell Sort, explaining their mechanisms and implementations. Additionally, it includes links for further resources on sorting algorithms.

Uploaded by

advika.sagar
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
You are on page 1/ 24

Data Structures

Div B
SY EXCP
Sem III
Dr. Rajashree Daryapurkar
2023-24
Sorting Algorithms
Sorting
• Sorting means arranging the elements of an
array so that they are placed in some relevant
order which may be either ascending or
descending
• A sorting algorithm is defined as an algorithm
that puts the elements of a list in a certain
order, which can be either numerical order,
alphabetical order, or any user-defined order.
Sorting
• Internal sorting which deals with sorting the
data stored in the computer’s memory
• External sorting which deals with sorting the
data stored in files.
• External sorting is applied when there is
voluminous data that cannot be stored in the
memory.
Sorting
• Merge Sort is a Divide and Conquer algorithm.
• It divides input array in two halves, calls itself for
the two halves and then merges the two sorted
halves.
• The merge() function is used for merging two
halves. The merge(arr, l, m, r) is key process that
assumes that arr[l..m] and arr[m+1..r] are sorted
and merges the two sorted sub-arrays into one.
Merge Sort
Merge Sort
Merge Sort
Merge Sort
Merge Sort
Merge Sort
Merge sort implementation
MergeSort(arr[], l, r)
If l < r
1. Find the middle point to divide the array into two
halves: middle m = l+(r-l)/2
2. Call mergeSort for first half: Call mergeSort(arr, l,
m)
3. Call mergeSort for second half: Call mergeSort(arr,
m+1, r)
4. Merge the two halves sorted in step 2 and 3: Call
merge(arr, l, m, r)
Insertion Sort
Insertion sort is a simple sorting algorithm that
works the way we sort playing cards in our hands.
Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted
sequence arr[0…i-1]
Algorithm for insertion sort
• INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for K = 1 to N – 1
Step 2: SET TEMP = ARR[K]
Step 3: SET J = K - 1
Step 4: Repeat while TEMP <= ARR[J]
SET ARR[J + 1] = ARR[J]
SET J = J - 1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
Shell Sort
• ShellSort is mainly a variation of Insertion
Sort. In insertion sort, we move elements only
one position ahead.
• When an element has to be moved far ahead,
many movements are involved.
• The idea of shellSort is to allow exchange of
far items.
Shell Sort
Shell Sort
Shell Sort
Shell Sort
Shell Sort
Links for sorting algorithms
• https://www.geeksforgeeks.org

You might also like