Scribd
Upload
13 views

Sorting

sorting techniques

Uploaded by

Sneha Thyagarajan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views

Sorting

sorting techniques

Uploaded by

Sneha Thyagarajan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Bubble sort

 works by repeatedly swapping the adjacent elements if they are in the wrong order.

Algorithm

 traverse from left and compare adjacent elements and the higher one is placed at right side.

 In this way, the largest element is moved to the rightmost end at first.

 This process is then continued to find the second largest and place it and so on until the data
is sorted.

Time Complexity: O(N2)


Auxiliary Space: O(1)

Selection sort

 works by repeatedly selecting the smallest (or largest) element from the unsorted portion of
the list and moving it to the sorted portion of the list.

Time Complexity: O(N2)


Auxiliary Space: O(1)

Insertion Sort

 works by iteratively inserting each element of an unsorted list into its correct position in a
sorted portion of the list
 It is a stable sorting algorithm, meaning that elements with equal values maintain their
relative order in the sorted output.
Best case: O(n)
Worst case: O(n 2 )
Auxiliary Space: O(1)

Merge Sort

 follows the divide and conquer approach. It works by recursively dividing the input array into
smaller subarrays and sorting those subarrays then merging them back together to obtain
the sorted array.

Time Complexity: O( n log n)


Auxiliary Space: O(N)

Quick Sort
 follows the divide and conquer that picks an element as a pivot and partitions the given array
around the picked pivot by placing the pivot in its correct position in the sorted array.

Time Complexity: O( n log n)


Auxiliary Space: O(1)

You might also like