In selection sort, if we have two duplicate elements, what is the behavior of the algorithm?

insertion sort
selection sort time complexity analysis
merge sort
selection sort program in c
bubble sort
selection sort stable
selection sort best case
selection sort java

If we delete the part starting with if (indexMax != i) from the code below (the last part) the Algoritm shatters, why?

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int indexMax = i;

        for (int j = i + 1; j < array.length; j++) {
            if (array[indexMax] < array[j]) {
                indexMax = j;
            }
        }

        if (indexMax != i) {
            int temp = array[i];
            array[i] = array[indexMax];
            array[indexMax] = temp;
        }
    }
}

Your code would do the following:

arr[] = 1, 5, 2, 4, 3

// find the max from arr[0..4]
// substitute it with the index 0, if it is not of that index already
arr[] = 5, 1, 2, 4, 3

// find the max from arr[1..4]
// substitute it with the index 1, if it is not of that index already
arr[] = 5, 4, 2, 1, 3 

// find the max from arr[2..4]
// substitute it with the index 2, if it is not of that index already 
arr[] = 5, 4, 3, 1, 2

// find the max from arr[3..4]
// substitute it with the index 3, if it is not of that index already 
arr[] = 5, 4, 3, 2, 1

The substitute it with the index i, if it is not of that index already is that if statement


For a longer array, with duplicates, check this Kotlin Playground Code I created for you. You can change the array as you wish, and you can trace the switching of the values.

Selection sort, In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n2) The algorithm divides the input list into two parts: a sorted sublist of items The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort. How does selection sort handle duplicate values in arrays? I'm having a hard time finding the answer online. If I have an array like [8, 4, 7, 3, 9, 3] then which index will selection sort choose to swap with on the first pass of the array?

From the code you posted with my comments:

    int indexMax = i;  // initial value of indexMax

    for (int j = i + 1; j < array.length; j++) {
        // please note that j starts with (i+1)
        if (array[indexMax] < array[j]) {
            indexMax = j;  // index of Max candidate  
        }
    }

    if (indexMax != i) {   // means that the above loop reassigned indexMax
        int temp = array[i];  // so we are swapping
        array[i] = array[indexMax];
        array[indexMax] = temp;
    }

So if (indexMax != i) means "Did we find a better Max?"

Sorting, Computational complexity (worst, average and best behavior) of element A comparison sort examines the data only by comparing two elements with a comparison operator. General methods: insertion, exchange, selection, merging, etc. But if there are equal keys, then a sorting algorithm is stable if whenever there are� Each scan performs three comparisons per two elements (a pair of elements is compared, then the greater is compared to the maximum and the lesser is compared to the minimum), a 25% savings over regular selection sort, which does one comparison per element. Sometimes this is double selection sort. Selection sort can be implemented as a stable

In the picture you can see how duplicate items move their relative position.This introduce instability.

For three duplicate items:

For two duplicate items:

5.4.1 Selection sort, The operation of the selection sort algorithm can be visualized by imagining a list to the end of the sorted list is repeated over and over until the input list is empty . illustrates the behavior of the selection sort algorithm on a list of eight items. For eight items, we have 1/2(82 + 8) = 1/2(64 + 8) = 1/2(72) = 36 comparisons. Java Program to perform Selection Sort on Array. In the following example, we have defined a method selectionSort() that implements the selection sort algorithm. It finds the minimum element from the array and swaps it with the first element of the array. We have created another method printArr() to display the elements of the array. We have

Horstmann Chapter 14, When the unsorted portion is of length 1, we are done In selection sort, pick the smallest element and swap it with the first one. Pick the smallest element Section 7.3.6 has two algorithms for removing an element from an array of length n. How many That worst-case behavior occurs when the input set is already sorted� Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

4. Sorting Algorithms, If there are duplicate elements, these elements must be contiguous in the resulting Information stored in RAM typically takes one of two forms: pointer- based or value-based. Selection Sort is the slowest of all the sorting algorithms described in this Heap Sort shows how to apply this behavior to sort a set of elements. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass.

Chapter 11: Sorting Algorithms and Analysis, If i is 9 and we compare i with i+1, there would be an error since the array slot 10 is nonexistent. When two items are not in order, a swap is necessary to sort the items. STRAIGHT SELECTION SORT ALGORITHM: SIMPLIFIED up with formulas that describe the behaviors of each sorting algorithm in best, average and� 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.

Comments
  • Do you know what that part does?
  • That part of the algorithm is the part that actually swaps the Max with the current index in order to sort it...
  • cause that's the part that makes the permutations? Your question is unclear. You can't remove random part of a code and expect it to still work the same way
  • To answer the question from the title: give it a try, it's way faster than waiting for an answer
  • if (indexMax != i) is just betterment of the algo .. if you debug it with already sorted array it will never get called ,.. hence you save the swapping.
  • Please give an example with two duplicate elements @Nizar
  • Alright, I'll update my answer with a duplicate element. Be right back.
  • I updated my answer for you Hadi, kindly check it. As PM mentioned, if two elements are equal then the arr[m] < arr[j] would return false; therefore, the swap will not happen.
  • My question is how do the algorithm work if we have two duplicates in the array please trace for me :0
  • For tracing in your case please use a debugger with step-by-step execution.
  • If two elements are equal than array[indexMax] < array[j] will be false and no swap will happen.
  • I think you got voted down because you have this backwards. It is sorting largest to the left. Other than that, I love that you drew it out. The other ones are more accurate but for people that are visual and still trying to understand code, this is a great description. @ me if you change it so that the array becomes largest to smallest and I'll up-vote your answer. (Take a look at the Kotlin link in the accepted answer)
  • Updated @Rodger