Inspiration

MLH GHW Challenge

What it does

A ** Sorting Algorithm** is used to rearrange a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure.

*Bubble Sort * is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

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. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

The algorithm maintains two subarrays in a given array.

The subarray which already sorted. The remaining subarray was unsorted. In every iteration of the selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the beginning of unsorted subarray.

After every iteration sorted subarray size increase by one and unsorted subarray size decrease by one.

How we built it

Bubble Sort

Follow the below steps to solve the problem:

Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1 If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on

Print the sorted array

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 sorted.

Insertion Sort

To sort an array of size N in ascending order:

Iterate from arr[1] to arr[N] over the array. Compare the current element (key) to its predecessor. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Code

1. 'Bubble' int main(){ int n,temp; cin>>n; int arr[n]; for(int i=0; i<n;i++){ cin>>arr[i]; } int counter=1; while(counter<n){ for(int i=0;i<n-counter;i++){ if(arr[i]>arr[i+1]){ int temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } counter++; } for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl; return 0; }
2. 'Selection' int main(){ int n,temp; cin>>n; int arr[n]; for(int i=0; i<n;i++){ cin>>arr[i]; } for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(arr[j]<arr[i]){ temp=arr[j]; arr[j]=arr[i]; arr[i]=temp; } } } for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } cout<<endl; return 0; }
3. 'Insertion' ```int main(){ int n,temp; cin>>n; int arr[n]; for(int i=0; i>arr[i]; } for(int i=1;icurrent&&j>=0){ arr[j+1]=arr[j]; j--; } arr[j+1]=current; } for(int i=0; i<n;i++){ cout<<arr[i]<<" "; } cout<<endl;

return 0; }```

Accomplishments that we're proud of

Time Complexity (Worst Case) Bubble Sort O(n^2) Selection Sort O(n^2) Insertion Sort O(n^2)

What we learned

We always check for Worst Case rather than Best and Average Case. Its good to know the best and the Average Case but the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size n, and thus guarantees that the algorithm will finish in the indicated period of time.

What's next for Sorting Method

1.Merge Sort 2.Quick Sort 3.Heap Sort 4.Radix Sort 5.Bucket Sort

Built With

• cpp