CODEWITHSUNDEEP
algorithmsorting
xitas
xitas

Reputation: 1164

Selection Sort algorithm

Selection Sort:

sorting algorithm

I have created a selection sorting algorithm but someone said to me its not right selection sort.

If its not right so what type of sorting is it? and how it is different then selection sorting.

Code:

void selection_Sort(int arr[] , int size){
    int temp , length = size;
    for(int i = 0; i < size ; i++){
        for(int j = i + 1; j < size ; j++){
            if(arr[i] > arr[j]){
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }   
        }
    }
}

please tell me how can i improve it?

Upvotes: 0

Views: 5300

Answers (8)

Saubhagya Sathsarani
Saubhagya Sathsarani

Reputation: 1

In selection sort find the smallest element first, then swap it correct position in one operation. In this code swap elements during the comparison.

Upvotes: 0

Paurav Shah
Paurav Shah

Reputation: 51

Selection Sort in C

Selection sort is basically selecting the very first element of your unsorted sub-array as a minimum and comparing it with the other elements of your sub-array to find your original minimum. Then, replacing that minimum element with the first element of your sub-array. That's all!

Here goes my code...

#include <stdio.h>

void selectionSort(int n){
    int arr[n],i,j,minIndex;

    printf("\nInsert %d elements:\n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("Insert complete.\n\n");

    printf("Your array looks like:\n");
    for(i=0;i<n;i++){
        printf("%d ",arr[i]);
    }

    //Selection Sort Algorithm
    for(i=0;i<n-1;i++){
        minIndex = i;
        for(j=i+1;j<n;j++){
            if(arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        //Swapping elements
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    printf("\n\nAfter sorting your array looks like:\n");
    for(i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
}

int main(){
    int n;
    printf("Enter number of array elements: ");
    scanf("%d",&n);
    selectionSort(n);
    return 0;
}

Result: -

enter image description here

Upvotes: 0

user6184932
user6184932

Reputation:

Selection Sort in Javascript

Comparing each with the rest and swapping with the smallest from the rest Try this code here: https://repl.it/@VinitKhandelwal/selection-sort-javascript

function selectionSort(arr){
  let min;
  let i;
  let j;
  let temp;
  console.log("Input Array");
  console.log(arr);
  for (i = 0; i < arr.length-1; i++) {
    min = i;
    for (j = i+1; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
      if (arr[j] < arr[min]) {
        console.log(arr[j]);
        min = j;
      }
    }
    if (min !== i) {
      temp = arr[min];
      arr[min] = arr[i];
      arr[i] = temp;
      console.log(arr);
    } 
  }
  console.log("Sorted using Selection Sort");
  return arr
}
console.log(selectionSort([5,7,6,9,8,2,1,4,3]));
// console.log(selectionSort([1,2,3,4,5,6,7,8,9])); // uncomment to try best case, i.e. sorted

Upvotes: 1

Omkar
Omkar

Reputation: 111

You have to implement a minimum element after outer for loop. Here is the code:

def selectionSort(arr):

for i in range(len(arr)):

# Find the minimum element in remaining 
# unsorted array
min_idx = i
for j in range(i+1, len(arr)):
  if arr[min_idx] >  arr[j]:
    min_idx = j

# Swap the found minimum element with 
# the first element        
arr[i], arr[min_idx] = arr[min_idx], arr[i]

return arr arr = [7,4,5,9,8,2,1]

print(selectionSort(arr))

How Selection sort works?

  1. Starting from the first element, we search the smallest element in the array, and replace it with the element in the first position.
  2. We then move on to the second position, and look for smallest element present in the subarray, starting from index 1, till the last index.
  3. We replace the element at the second position in the original array, or we can say at the first position in the subarray, with the second smallest element. 4.This is repeated, until the array is completely sorted.

Upvotes: 1

Tharaka Rumesh Jeewantha
Tharaka Rumesh Jeewantha

Reputation: 182

You can improve it this way:

void selectionSort(double array[], int size) {
    int min;
    double temp;
    for (int step = 0; step < size-1; step++)  {
        min =  step;
        for (int i = step+1; i < size; i++) {
            if (array [i] < array[min])   {
                min = i;
            }
        }
        temp = array[step];
        array [step] = array[min];
        array [min] = temp;
    }

Upvotes: 0

Selim Reza
Selim Reza

Reputation: 1084

        var Selectionsort = function (A) {
            for (var i = 0; i < A.length; i++) {
                var imin = i;
                    for (var j = i + 1; j <= A.length; j++) {
                        if (A[j] < A[imin]) 
                            imin = j;
                    }
                    var tmp = A[i];
                    A[i] = A[imin];
                    A[imin] = tmp;
            }
            return A;
        };
        var A = [10, 20, 30, 40, 50, 60, 70, 80];
        var Aftersorted = Selectionsort(A);
        console.log(Aftersorted);

Upvotes: 0

libik
libik

Reputation: 23029

You have implemented Bubble sort.

The selection sort means you should find the lowest(or bigest) element in inner cycle and then switch it with element to the left/right which is at the edge of selecting (like in the picture).

There are three similar sorting alghoritms - select sort, insert sort and bubble sort you can watch how they behave here : https://i.sstatic.net/LT5k9.gif

Upvotes: 1

MBo
MBo

Reputation: 80187

To transform this code into selection sort, you have to find index of minimal element in the inner cycle, and exchange element at this index with i-th element after inner cycle finishes.

So overall number of swaps does not exceed N (while your current code could produce about N^2/2 swaps)

Upvotes: 3

Related Questions