Data Structure – Selection Sort

in this sort, it’s very much like bubble sort since in bubble the largest element should be in the RIGHT side, in Selection sort we are looking for SMALLEST items and select that then find its proper location which will be the most LEFT side and REPLACE it with whatever in that location.

still, LEFT side is smallest and right side has the largest, but the number os swaps are decreased however to find the proper location we have to do a lot of comparisons.

Orders:

  • the worst case scenario O(N^2)
  • average case scenarios O(N^2) –> but in practice
  • Selection sort is better than Bubble sort,
  • Selection sort is worse than Insertion sort,
  •  best case scenario O(N^2) — since it has lots of comparisons.

where to use:

  • not good for large unsorted data sets, and in General.
  • since it has a few swaps N, it might be good in cases where the cost of Comparisons is cheaper than swaps.
  • from space and memory perspectives, since it’s working on the array, itself, it’s good.

how to code:

/**
*
* @author Navid_
*/
public class SelectionSort {

public static int[] myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};

/**
* resetting array content to what it was.
*/
public static void resetData() {
myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};
}

/**
* showing content of array
*
* @param arr
*/
public void showContent(int[] arr) {

System.out.print("[ ");
for (int i : arr) {
System.out.printf("%d, ", i);
}
System.out.println(" ]");
}

public static void main(String[] args) {
SelectionSort ss = new SelectionSort();

ss.showContent(SelectionSort.myArray);
ss.sort(SelectionSort.myArray);
ss.showContent(SelectionSort.myArray);

}

public void sort(int[] myArray) {

for (int i = 0; i < myArray.length; i++) {
//find smallest
int smallestIndex = searchToFindSmallest(myArray, i, myArray.length);

// now repalce the smallest with the next item in the unsorted array
swap(myArray, smallestIndex, i);

showContent(myArray);
}

}

/**
* smallest item index will be returned.
*
* @return
*/
public int searchToFindSmallest(int[] arr, int startSearch, int limitSearch) {

int smallest = startSearch;
boolean foundSthNew = false;
for (int index = startSearch; index < limitSearch; index++) {
if (arr[index] < arr[smallest]) {
// so we find something smaller
System.out.printf("Found a samllest item ... arr[%d]=%d\n",index,arr[index] );
smallest = index;
foundSthNew = true;
}
}

if (foundSthNew) {

return smallest;
} else {
return -1;
}
}

private void swap(int[] myArray, int smallestIndex, int i) {

int tmp = 0;
if (smallestIndex == -1) {
System.out.println("no swapping anymore.\n");
return;
}
tmp = myArray[i];
myArray[i] = myArray[smallestIndex];
myArray[smallestIndex] = tmp;
System.out.printf("Swapping arr[%d]=%d with arr[%d]=%d\n",i,myArray[i],smallestIndex,myArray[smallestIndex]);
}

}

and it’s output will be something like this …

run:
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[1]=2
Swapping arr[0]=2 with arr[1]=10
[ 2, 10, 5, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[2]=5
Swapping arr[1]=5 with arr[2]=10
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[7]=5
Swapping arr[2]=5 with arr[7]=10
[ 2, 5, 5, 20, 90, 12, 31, 10,  ]
Found a samllest item ... arr[5]=12
Found a samllest item ... arr[7]=10
Swapping arr[3]=10 with arr[7]=20
[ 2, 5, 5, 10, 90, 12, 31, 20,  ]
Found a samllest item ... arr[5]=12
Swapping arr[4]=12 with arr[5]=90
[ 2, 5, 5, 10, 12, 90, 31, 20,  ]
Found a samllest item ... arr[6]=31
Found a samllest item ... arr[7]=20
Swapping arr[5]=20 with arr[7]=90
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
no swapping anymore.
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
no swapping anymore.
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)
Advertisements

One thought on “Data Structure – Selection Sort

  1. Pingback: Data Structure – Sorting Algorithms in Java | Navid's Thoughts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s