[Sort] Selection Sort (선택 정렬)

Selection Sort (선택 정렬)

- Python - 

def selection_sort(collection):

    print('----- Selection Sort -----')

    print('input : ' + str(collection))

    for i in range(len(collection)-1, 0, -1):

        pos_max = 0

        for j in range (1, i+1):

            if collection[pos_max] < collection[j]:

                pos_max = j

        if(pos_max is not i): #if position is same, swap is unnecessary

            collection[pos_max], collection[i] = collection[i], collection[pos_max]

        print(str(len(collection) - i)+ 'th progressing ... ' + str(input))

    return collection

input = [3, 8, 6, 5, 4, 2, 1, 7]

result = selection_sort(input)

print('\nresult : ' + str(result))

Result

- Javascript -

function selctionSort(array) {

console.log("----- Selection Sort -----");

console.log(`input : ${array}`);

let input = array;

for(let i = input.length - 1; i > 0; i--) {

let posMax = 0;

for(let j = 1; j <= i; j++) {

if(input[j] > input[posMax]) posMax = j;

}

if(posMax !== i) { // if position is same, swap is unnecessary

let tmp = input[i];

input[i] = input[posMax];

input[posMax] = tmp;

}

console.log(`${input.length - i}th progressing ... ${input}`);

}

return input;

}

let input = [3, 8, 6, 5, 4, 2, 1, 7];

let result = selctionSort(input);

console.log(`\nresult : ${result}`);

Result

*** if posMax and i are at the same position, swap is unnecessary. but using <if> can make more time complexity.

It depends on the order of data input and size. So it's OK to just remove that <if> statement.