Last active
September 30, 2017 05:49
-
-
Save anil477/438cdf134344207a9dffdc6f9171f70b to your computer and use it in GitHub Desktop.
Selection Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Best - O(n^2) | |
// Average - O(n^2) | |
// Worst - O(n^2) | |
// Space - O(1) | |
class SelectionSort | |
{ | |
void sort(int arr[]) | |
{ | |
int n = arr.length; | |
// One by one move boundary of unsorted subarray | |
// wo don't need to check the (n-1)th element, as it will by itself fall in place | |
for (int i = 0; i < n-1; i++) | |
{ | |
// Find the minimum element in unsorted array | |
int min_idx = i; | |
// we j<n because we need to check every element till the last(inclusive) | |
for (int j = i+1; j < n; j++) | |
if (arr[j] < arr[min_idx]) | |
min_idx = j; | |
// Swap the found minimum element with the first element | |
int temp = arr[min_idx]; | |
arr[min_idx] = arr[i]; | |
arr[i] = temp; | |
} | |
} | |
// Prints the array | |
void printArray(int arr[]) | |
{ | |
int n = arr.length; | |
for (int i=0; i<n; ++i) | |
System.out.print(arr[i]+" "); | |
System.out.println(); | |
} | |
// Driver code to test above | |
public static void main(String args[]) | |
{ | |
SelectionSort ob = new SelectionSort(); | |
int arr[] = {64,25,12,22,11}; | |
ob.sort(arr); | |
System.out.println("Sorted array"); | |
ob.printArray(arr); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment