Reputation: 1401
Java - Selection Sort Algorithm
I have some questions about selection sort.I'm a little bit confused.
int [] arr = {5,4,3,2,1}; // This is my array
int min = 0;
for(int i = 0;i<arr.length;i++)
{
//Assume first element is min
min = i;//Selection sort algorithm says that find the minimum in the
// array, but first element is not minimum.What's point here?
for(int j = i + 1;j<arr.length;j++)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
System.out.println(arr[i]);//I print the in ascending order
}
}
Output is :
4
3
2
1
4
3
2
4
3
4
What's wrong ?
Upvotes: 4
Views: 77453
Answers (19)
Reputation: 1
import java.util.*;
public class Sorting{
public static void main(String[]args){
long startTime;
long selectionTime;
long bubbleTime;
long insertionTime;
long parallelTime;
long quickTime;
int[]copy = shuffle();
int[]copy1 = Arrays.copyOf(copy,100000);
int[]copy2 = Arrays.copyOf(copy,100000);
int[]copy3 = Arrays.copyOf(copy,100000);
int[]copy4 = Arrays.copyOf(copy,100000);
int[]copyD = descending();
int[]copy5 = Arrays.copyOf(copyD,100000);
int[]copy6 = Arrays.copyOf(copyD,100000);
int[]copy7 = Arrays.copyOf(copyD,100000);
int[]copy8 = Arrays.copyOf(copyD,100000);
System.out.println("************** SORT RESULTS (millis) **************" + "\n" + "\n");
System.out.print("[Bubble]");
startTime = System.currentTimeMillis();
bubbleSort(ascending());
bubbleTime = System.currentTimeMillis() - startTime;
System.out.print(" Ascending: " + bubbleTime + " ");
startTime = System.currentTimeMillis();
bubbleSort(copyD);
bubbleTime = System.currentTimeMillis() - startTime;
System.out.print(" Descending: " + bubbleTime + " ");
startTime = System.currentTimeMillis();
bubbleSort(copy);
bubbleTime = System.currentTimeMillis() - startTime;
System.out.print(" Shuffled: " + bubbleTime + " ");
System.out.println("\n");
System.out.print("[Selection]");
startTime = System.currentTimeMillis();
selectionSort(ascending());
selectionTime = System.currentTimeMillis() - startTime;
System.out.print(" Ascending: " + selectionTime + " ");
startTime = System.currentTimeMillis();
selectionSort(copy5);
selectionTime = System.currentTimeMillis() - startTime;
System.out.print(" Descending: " + selectionTime + " ");
startTime = System.currentTimeMillis();
selectionSort(copy1);
selectionTime = System.currentTimeMillis() - startTime;
System.out.print(" Shuffled: " + selectionTime + " ");
System.out.println("\n");
System.out.print("[Quick]");
startTime = System.currentTimeMillis();
quick(ascending());
quickTime = System.currentTimeMillis() - startTime;
System.out.print(" Ascending: " + quickTime + " ");
startTime = System.currentTimeMillis();
quick(copy6);
quickTime = System.currentTimeMillis() - startTime;
System.out.print(" Descending: " + quickTime + " ");
startTime = System.currentTimeMillis();
quick(copy2);
quickTime = System.currentTimeMillis() - startTime;
System.out.print(" Shuffled: " + quickTime + " ");
System.out.println("\n");
System.out.print("[Parallel]");
startTime = System.currentTimeMillis();
parallel(ascending());
parallelTime = System.currentTimeMillis() - startTime;
System.out.print(" Ascending: " + parallelTime + " ");
startTime = System.currentTimeMillis();
parallel(copy7);
parallelTime = System.currentTimeMillis() - startTime;
System.out.print(" Descending: " + parallelTime + " ");
startTime = System.currentTimeMillis();
parallel(copy3);
parallelTime = System.currentTimeMillis() - startTime;
System.out.print(" Shuffled: " + parallelTime + " ");
System.out.println("\n");
System.out.print("[Insertion]");
startTime = System.currentTimeMillis();
insertionSort(ascending());
insertionTime = System.currentTimeMillis() - startTime;
System.out.print(" Ascending: " + insertionTime + " ");
startTime = System.currentTimeMillis();
insertionSort(copy8);
insertionTime = System.currentTimeMillis() - startTime;
System.out.print(" Descending: " + insertionTime + " ");
startTime = System.currentTimeMillis();
insertionSort(copy4);
insertionTime = System.currentTimeMillis() - startTime;
System.out.print(" Shuffled: " + insertionTime + " ");
System.out.println("\n");
}
public static void selectionSort(int[] list)
{
for(int top = list.length - 1; top > 0; top--){
int largeLoc = 0;
for(int i = 1; i <= top; i++){
if(list[i] > list[largeLoc]){
largeLoc = i;
}
}
int temp = list[top];
list[top] = list[largeLoc];
list[largeLoc] = temp;
}
}
public static void bubbleSort(int[]list){
boolean swap = false;
do{
swap = false;
for(int i=0;i<list.length-1;i++){
if(list[i] > list[i+1]){
int temp = list[i];
list[i] = list[i+1];
list[i+1] = temp;
swap = true;
}
}
}while(swap != false);
}
public static void insertionSort(int[]list){
for(int i=0;i<list.length;i++){
int c = list[i];
int j = i - 1;
while(j >= 0 && list[j] > c){
list[j + 1] = list[j];
j--;
list[j + 1] = c;
}
}
}
public static void parallel(int[]list){
Arrays.parallelSort(list);
}
public static void quick(int[]list){
Arrays.sort(list);
}
public static int[] shuffle(){
int[] shuffleArray = new int[100000];
for(int i=0;i<100000;i++){
int rand=(int)(Math.random()*100000) + 1;
shuffleArray[i] = rand;
}
return shuffleArray;
}
public static int[] descending(){
int[]descendingArray=new int[100000];
int c=0;
for(int i=100000;i>=1;i--){
descendingArray[c] = i;
c++;
}
return descendingArray;
}
public static int[] ascending(){
int c1=0;
int[]ascendingArray=new int[100000];
for(int i=1;i<=100000;i++){
ascendingArray[c1] = i;
c1++;
}
return ascendingArray;
}
}
Upvotes: 0
Reputation: 29
Algorithm of selection sort.
- In the given array, get the 0th index as the minimum value.
- Next consider the remaining array to figure out whether any element is less than the given 0th index, then swap.
- process this same step for the next index 1st to nth, automatically it will get sorted.
The sample program as follows
class Sort{
private void selectionSort(Integer[] elements) {
for(int i=0;i<elements.length;i++) {
int minIndex = i;
for(int j=i+1;j<elements.length;j++) {
if(elements[minIndex]>elements[j]) {
minIndex = j;
}
}
int temp = elements[i];
elements[i] = elements[minIndex];
elements[minIndex] = temp;
}
}
public static void main(String arsgs[]) {
Integer[] elements = {5,4,3,2,1};
new Sort().selectionSort(elements);
Arrays.asList(elements).stream().forEach(System.out::println);
}
}
Upvotes: 0
Reputation: 1
Selection sort is a sorting algorithm in which the smallest element is picked from an unsorted array and moved to the beginning of the array. In your case first find min value index from second for loop and swap outside on that loop.
private static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
Upvotes: -1
Reputation: 983
Just pass array and size of array
private void selectionSort() {
for (int i = 0; i < arraySize; i++) {
for (int j = i; j < arraySize; j++) {
if (array[i] > array[j])
swapValues(i,j);
}
}
}
private void swapValues(int posOne, int posTwo) {
int tValue = array[posOne];
array[posOne] = array[posTwo];
array[posTwo] = tValue;
}
Upvotes: 0
Reputation: 1056
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted. 2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Example:
arr[] = 64 25 12 22 11
// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64
// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64
// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64
// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64
Java Code is:
void sort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
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;
}
}
And Be Clear that Arrays are Passed by Reference!
Upvotes: 0
Reputation: 1711
pass the unsorted array get the sorted array
public int[] selectionSort(int[] list) {
int i, j, minValue, minIndex, temp = 0;
for (i = 1; i < list.length; i++) {
minValue = list[i];
minIndex = i;
j = i - 1;
for (j = i; j < list.length; j++) {
if (list[j] < minValue) {
minValue = list[j];
minIndex = j;
}
}
if (list[i] > minValue) {
temp = list[i];
list[i] = list[minIndex];
list[minIndex] = temp;
}
}
return list;
}
Upvotes: 0
Reputation: 183
Selection sort is a algorithm that forming array elements in ANSI order or DENSI order. Best case, Average case and Worst case time complexity is (n2). Selection sort is not better for sorting an array... Selection sort implementation is given below:
import java.util.Scanner;
class selection{
public static void main(String a[]){
Scanner sc=new Scanner(System.in);
System.out.print("size :");
int n=sc.nextInt();
int i,j,tmp,minVal;
int[] ar=new int[n];
for(i=0;i<n;i++){
ar[i]=sc.nextInt();
}
for(i=0;i<(n-1);i++){
minVal=ar[i];
for(j=(i+1);j<n;j++){
if(minVal>ar[j]){
minVal=ar[j];
tmp=ar[i];
ar[i]=minVal;
ar[j]=tmp;
}
}
}
for(i=0;i<n;i++){
System.out.print(ar[i]+" ");
}
}
Upvotes: 0
Reputation: 445
public class Selectionsort{
public static int arr[]; public static int y;
public static void main( String args[] ){
System.out.println("Enter number of element you want to enter for sorting");
int nofele= Integer.parseInt(args[0]);
System.out.println("Enter number of element entered for sorting is "+ "\n" +nofele);
arr = new int[nofele];
System.out.println("Entered array is");
for(int i=1,j=0;i<=nofele;i++,j++){
arr[j]=Integer.parseInt(args[i]);
System.out.println(arr[j]);
}
System.out.println("Sorted array for selection sort is ");
for(int k=0;k<nofele-1;k++) {
for(int l=nofele-k,b=1;l>=2;l--,b++){
if(arr[k]>arr[k+b]){
int temp=arr[k];
arr[k]=arr[k+b];
arr[k+b] = temp;
}
}
System.out.println(arr[k]);
}
System.out.println(arr[nofele-1]);
}
}
Upvotes: 0
Reputation: 138
int[] arr = {5,4,3,2,1};
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
This is the correct method for selection sort The thing you have been doing wrong is you are swapping within the inner loop but actually the swapping needs to be done after the first complete round of inner loop where the minimum element is determined.
Upvotes: 0
Reputation: 29
/* Implementation of selection sort */
import java.util.Arrays;
import java.util.Scanner;
public class SelectionSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
System.out.println("Enter the number of elements of the array");
int n = in.nextInt();
int []a = new int[n];
System.out.println("Enter the integer array of elements");
for (int i=0; i<n ; i++)
{
a[i] = in.nextInt();
}
System.out.println("Before Sorting: "+Arrays.toString(a));
a = sort(a);
System.out.println("After Sorting: "+Arrays.toString(a));
}
private static int[] sort(int[] a) {
// TODO Auto-generated method stub
for(int i=0; i<a.length-1;i++)
{
int index=i;
for(int j=i+1; j<a.length;j++)
if(a[j]<a[index])
{
index=j;
}
int small = a[index];
a[index] = a[i];
a[i]=small;
}
return a;
}
}
Upvotes: 0
Reputation: 627
Assume a lowest element, which requires scanning the all elements and then swap it to the first position.
private static void selectionSortMethod(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) { //no of iterations for array length
for (int j = i + 1; j < arr.length; j++) { //starting from next index to lowest element(assuming 1st index as lowest)
if (arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
//print
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
Upvotes: 0
Reputation: 434
As mentioned earlier, you're not updating your 'min' variable in the inner loop. The objective of the inner loop is to find the index of the smallest element. You should also move the 'swap' to the outer loop. Below is the Selection Sort pseudo code:
Selection Sort
Inputs:
A: an array
n: the number of elements in A to sort
Procedure SELECTION-SORT (A, n)
1. For i = 0 to n – 1:
A. Set minIndex to i.
B. For j = i + 1 to n:
i. If A[j] < A[minIndex], then set minIndex to j. // Add this
C. Swap A[i] with A[minIndex]. // Move this to outside of the inner loop
Take a look at the link to my blog below to see a full explanation of the Selection Sort algorithm. There are implementations in Java, C++, Python, and JavaScript.
http://brianredd.com/algorithm/selection-sort
Upvotes: 0
Reputation: 121
public class SelectionSort {
public static void main(String[] args) {
int[] A = {5,4,3,2,1};
int l = A.length;
for (int i = 0; i < l-1; ++i ){
int minPos = i;
// Find the location of the minimal element
for (int j = i + 1; j < l; ++j){
if ( A[j] < A[minPos]){
minPos = j;
}
}
if (minPos != i){
int temp = A[i];
A[i] = A[minPos];
A[minPos] = temp;
}
}
System.out.println(Arrays.toString(A));
}
}
Upvotes: 0
Reputation: 1442
What is wrong is that in your inner loop you should update your index, using the strategy you follow of doing the swap in the inner loop I made a working selection sort:
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] input = new int[] {5,2,4,6,1,3};
System.out.println( Arrays.toString(selectionSort(input)) );
}
public static int[] selectionSort(int[] input) {
int length = input.length;
int minimumValue = Integer.MAX_VALUE;
for (int i = 0; i < length; ++i) {
// find the minimumValue when j > i and swap it with input[i] location
for (int j =i; j < length; ++j) {
if (input[j] <= minimumValue ) {
minimumValue = input[j];
input[j] = input[i];
input[i] = minimumValue;
}
}
minimumValue = Integer.MAX_VALUE;
}
return input;
}
}
I added to github.
Upvotes: 0
Reputation: 195109
selection sort is about finding the min value in each step of loop. you didn't find out the min value (by if statement maybe), just simply exchange the value in your inner loop. so you actually didn't do a sort.
correction based on your implementation:
final int[] arr = { 5, 4, 3, 2, 1 }; // This is my array
int min;
for (int i = 0; i < arr.length; i++) {
// Assume first element is min
min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
final int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
System.out.println(arr[i]);// I print the in ascending order
}
this should give you output:
1
2
3
4
5
Upvotes: 6
Reputation: 36611
You should first find the minimum instead of assuming the first element is the minimum
int[] array = {5, 4, 3, 2, 1};
for ( int i = 0; i < array.length; i++ ) {
//find minimum, starting from index i
int minIndex = i;
int min = array[i];
for ( int j = i + 1; j < array.length; j++ ) {
if ( array[ j ] < min ) {
minIndex = j;
min = array[j];
}
}
// now move the smallest element to the front, and the element at index i to the index of the minimal element
int temp = array[ i ];
array[ i ] = min;
array[ minIndex ] = temp;
}
Upvotes: 1
Reputation: 11543
You should start by assuming that the first element is the smallest one, then iterate over the array and if you find a smaller element, remember that position and assume that is the smallest one. When you get to the end of the array you should know the position of the smallest value. Switch that value with the value at the first position. Now the smallest value is first. Start at next position, assume that is the smallest value, iterate over the rest of the array... (I think you get the idea.
Example:
3,1,2
Assume 3 (pos 1) is smallest. Compare with position 2, 1 < 3, so assume position 2 has smallest value. Compare with position 3, 3 < 1. Since we are at the end switch smallest with first position. (position 1 and 2)
1,3,2
Now, since position 1 is done, start with position 2. Assume 3 (position 2) is the smallest value. Compare with position 3 (2). 2 < 3, so assume position 3 has smallest value. Since we are at the end of the array we switch position 2 and 3
1,2,3
Done
Upvotes: 0
Reputation: 82579
Your question appears to be in your comment
min = i;//Selection sort algorithm says that find the minimum in the
// array, but first element is not minimum.What's point here?
The point of that is you can assume the first one you're checking is the lowest just so you have a place to start from. After all, it might not be the minimum over all, but of the one's you've checked in this iteration, it's the lowest so far!
Upvotes: 2
Reputation: 14740
Correct:
public class Test {
public static void main(String args[]){
int[] arr = {5,4,3,2,1}; // This is my array
int min = 0;
for(int i = 0;i<arr.length;i++)
{
//Assume first element is min
min = i;
for(int j = i + 1;j<arr.length;j++)
{
if(arr[j] < arr[min]) { min = j;}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
System.out.println(arr[i]);//I print the in ascending order
}
}
}
About the min part: it just refers to the index of whatever is the current min. You move on down the array until you meet the new min, and set min to that index. So 5 is the minimum number [min =0] until you see 4 [so now min =1] but then you compare 3 to whatever is stored at 4 [when min=1] and then realize that you should set min=2.... etc. etc.
Upvotes: 3
Related Questions
- Valid selection sort algorithm?
- Need help understanding Selection Sort Algorithm
- selection sort Algorithm java
- Selection Sort, For Java
- Selection sort Algorithm in Java
- Selection Sort (Java)
- Java Selection Sort Modification
- Sorting with Selection
- Implementation of selection sort in Java
- Implementing Selection Sort in Java