[go: up one dir, main page]
Scribd
Upload
23 views18 pages

Sort Algo by Dr. Arun Parakh

Uploaded by

umakantchachondiya01
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 views18 pages

Sort Algo by Dr. Arun Parakh

Uploaded by

umakantchachondiya01
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/ 18

Sorting Algorithms

Dr. Arun Parakh


Professor
Department of Electrical Engineering
Shri G.S. Institute of Technology and Science, Indore (MP)-India
Sorting Terminology
●
In-place sorting (Insertion, Selection)
●
Internal Sorting (bubble, selection, quick, insertion)
●
External Sorting (Merge)
●
Stable and Unstable Sorting Algorithms
– Stable Algos: bubble, selection, merge , insertion
– Unstable Algos: Quick Sort
●
Complexities:
Time Complexity
Space Complexity
Types Of Time Complexity :
●
Best Time Complexity
●
Average Time Complexity
●
Worst Time Complexity
Compexities of different Algos
Space
Time complexity
Sorting Complexity
Algorithmes
Best Average Worst Worst

Selection Ω (n^2)) θ (n^2)) O(n^2)) O(1)

Insertion Ω (n) θ (n^2)) O(n^2)) O(1)

Bubble Ω (n) θ (n^2)) O(n^2)) O(1)

Merge Ω (n log(n)) θ (n log(n)) O(n log(n)) O(n)

Quick Ω (n log(n)) θ (n log(n)) O(n^2)) O(n)


Bubble Sort Algorithm
Bubble Sort is the simplest sor ting algorithm
that works by repeatedly swapping the adjacent
elements if they are in the wrong order.
Input : arr[] = {5, 1, 4, 2), 8}

First Pass : ( 5 1 4 2) 8 ) –> ( 1 5 4 2) 8 )


( 1 5 4 2) 8 ) –> ( 1 4 5 2) 8 )
( 1 4 5 2) 8 ) –> ( 1 4 2 5 8 )
( 1 4 2) 5 8 ) –> ( 1 4 2) 5 8 )
Second Pass : ( 1 4 2) 5 8 ) –> ( 1 4 2) 5 8 )
( 1 4 2) 5 8 ) –> ( 1 2 4 5 8 )
( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
Third Pass : ( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
( 1 2) 4 5 8 ) –> ( 1 2) 4 5 8 )
C Program for Bubble Sort
// C program for implementation of Bubble sort
#include <stdio.h>
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
/ Last i elements are already in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
C Program for Bubble Sort
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program to test above functions

int main()
{
int arr[] = { 64, 34,2)5, 12), 2)2), 11, 90 };
int n = sizeof(arr) / sizeof(arr[0]);}
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Selection sort
The selection sort algorithm sorts an array by repeatedly
finding the minimum element (considering ascending
order) from the unsorted part and putting it at the
beginning.
●
The algorithm maintains two subarrays in a given array.
1) The subarray which already sor ted.
2)) The remaining subarray was unsor ted.
●
In every iteration of the selection sort, the minimum
element (considering ascendingorder) from the unsorted
subarray is picked and moved to the sorted subarray.
Selection sort
Follow the below steps to solve the problem:
●
Initialize minimum value(min_idx) to location 0.
●
Traverse the array to find the minimum element in the
array.
●
While traversing if any element smaller than min_idx is
found then swap both the
●
values.
●
Then, increment min_idx to point to the next element.
●
Repeat until the array is sor ted.
Selection sort
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)


{
int i, j, min_idx;

// One by one move boundary of unsorted subarray


for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first element


if(min_idx != i)
swap(&arr[min_idx], &arr[i]);
}
}.
Insertion Sort
The array is virtually split into a sorted and an
unsorted part. Values from the unsorted part are
picked and placed in the correct position in the
sorted part.
Insertion Sort
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key, to one
position ahead of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Merge Sort
●
In simple terms, we can say that the process of
merge sort is to divide the array into two halves,
sort each half, and then merge the sorted halves
back together. This process is repeated until the
entire array is sorted.
Merge Sort
// l is for left index and r is right index of the
// sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2);

// Sort first and second halves


mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}
Merge Sort
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2) = r - m;

// Create temp arrays


int L[n1], R[n2)];

// Copy data to temp arrays L[] and R[]


for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2); j++)
R[j] = arr[m + 1 + j];
Merge Sort
// Merge the temp arrays back into arr[l..r
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
Merge Sort
// Copy the remaining elements of L[],
// if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of R[],


// if there are any
while (j < n2)) {
arr[k] = R[j];
j++;
k++;
}
}
Thank You

References:
●
https://www.geeksforgeeks.org
●

You might also like