Dsa – data structure and algorithms sorting

Data Structure and Algorithms-Sorting Algorithms Prepared By, S.Sajini AP/CSE

Sorting • A sorting algorithm is an algorithm used to generate the ordered list in a certain order. • Sorting is defined as ordering of given data based on different sorting technique Unsorted list Sorted list

Sorting Techniques ✔ Bubble sort ✔ Insertion sort ✔ Select sort ✔ Quick sort ✔ Merge sort ✔ Radix sort

Bubble Sort ✔ Bubble sort, is referred as sinking sort it is the simple sorting algorithm. ✔ Swapping with adjustment element in the list. Until no further swapping is needed which denoted all the elements as sorted in the list ✔ The sorting order is small element to largest number like the bubble in the given image

Algorithm procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length( A ) - 1 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure

Time Complexities Cases Big – O Best O ( n ) Average O ( n2 ) Worst O ( n2 )

Insertion Sort All the data items arranged in one at a time using Insertion sort algorithm

Algorithm insertionSort(array A) for i = 1 to length[A]-1 do begin value = A[i] j = i-1 while j >= 0 and A[j] > value do begin swap( A[j + 1], A[j] ) j = j-1 end A[j+1] = value end

Selection Sort Selection sort worked based comparison between the element

Algorithm for i = 1:n, k = i for j = i+1:n, if a[j] < a[k], k = j → invariant: a[k] smallest of a[i..n] swap a[i,k] → invariant: a[1..i] in final position end

Time Complexities Cases Big – O Best O ( n2 ) Average O ( n2 ) Worst O ( n2 )

Quick Sort • Element is picked is knows as pivot element . partitions the given array based on pivot element There are many different versions of quickSort that pick pivot in different ways. 1.Always pick first element as pivot. 2.Always pick last element as pivot (implemented below) 3.Pick a random element as pivot. 4.Pick median as pivot.

Algorithm function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // Move pivot to end storeIndex := left for i fromleft to right ? 1 if array[i] ? pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex

Algorithm procedure quicksort(array, left, right) if right > left select a pivot index (e.g. pivotIndex := left) pivotNewIndex := partition(array, left, right, pivotIndex) quicksort(array, left, pivotNewIndex - 1) quicksort(array, pivotNewIndex + 1, right)

• Quicksort(A[0….n-1],low,high) • { • If(low<high) • { • Mpartition(A[low….high]) • Quicksort(A[low….mid-1]) • Quicksort(A[]) • }

Partition(A[low…high] Pivot i J while(i<=j) do { while() do while() If(i<=j)then Swap() } Swap()//when I crosses j return j

Time complexity • T(n)=T(n/2)+T(n/2)+f(n)

Time Complexities Cases Big – O Best O (n log n ) Average O (n log n ) Worst O ( n2 )

Merge Sort “MergeSort is based on Divide and Conquer algorithm. It divides given input array in to two halves, calls itself for the two halves and then merges the two sorted halves.”

Algorithm function mergesort(m) var list left, right, result if length(m) ? 1 return m var middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = mergesort(left) right = mergesort(right) result = merge(left, right) return result

Algorithm function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ? first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result

Time Complexities Cases Big – O Best O (n log n ) Average O (n log n ) Worst O (n log n )

Radix Sort “Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value”

Algorithm RADIX_SORT (A, d) for i ← 1 to d do use a stable sort to sort A on digit i // counting sort will do the job

Time Complexities Cases Big – O Worst case time complexity O (n*k ) Worst Case space complexity O (n + k )

Example Following example shows how Radix sort operates on seven 3-digits number. Input 1st pass 2nd pass 3rd pass 329 720 720 329 457 355 329 355 657 436 436 436 839 457 839 457 436 657 355 657 720 329 457 720 355 839 657 839

Dsa – data structure and algorithms sorting

In this document

More Related Content

What's hot

Similar to Dsa – data structure and algorithms sorting

More from sajinis3

Recently uploaded

Dsa – data structure and algorithms sorting