선택정렬

배열

유사한 데이터들을 모아 놓은 것

배열로 저장하게 되면 메모리 인접한 공간을 할당받아 저장한다. 배열에 요소를 추가할 때 인접한 메모리가 다 차있으면 빈공간으로 요소들을 전부 데리고 이사한다.

연결리스트

유사한 데이터들의 메모리 주소를 연결시켜 놓은 것

데이터들을 메모리에 인접하게 저장하지 않고 따로따로 저장한다.

그 대신 현재 데이터가 다음데이터를 조회할 때 사용하기 위해 다음 데이터의 메모리 주소정보를 가지고 있는다.

메모리 공간을 연속적으로 차지 하지 않아 추가, 삭제 할 때 좋다.

특정 데이터를 읽기 위해서 해당 데이터 이전의 데이터들을 모두 읽어야 하기 때문에 특정 데이터만을 조회할 때는 효율이 않좋다.

배열은 메모리공간을 연속적으로 사용하기 때문에 임의의 데이터를 조회할 때는 속도가 빠르다.

배열 중간에 데이터를 삽입하거나 삭제하게 되면 삽입,삭제한 데이터 이후의 데이터들의 자리를 한칸 씩 이동시켜야 하기 때문에 낭비가 발생된다.

선택정렬

노래와 재생횟수가 같이 있는 목록이 있을 때 재생횟수가 많은 순으로 정렬하고자 한다.

ex>

a : 14

b : 4

c : 7

d : 10

e : 9

f : 3

가장 많이 들은 노래를 찾아서 현재 목록에서 잘라내서 새로운 텅빈 목록에 붙인다.

a 확인 → 14가 최대값인지 확인 → b확인 → 4가 최대값인지 확인 → ...

노래확인 O(n) , 재생횟수가 최대값인지 확인 O(n) ⇒ O(n^2)

python

targer_list = [5, 3, 6, 2, 10]

def selectionSort(arr: list) -> list:

    result = []

    while len(arr) > 0:

        maxValue = max(arr)

        arr.remove(maxValue)

        result.append(maxValue)

    return result

print(selectionSort(targer_list))

java

public class SelectionSort {

    private static void selectionSort(int[] array) {


        int temp;
        int maxIndex;
        for (int i = 0; i < array.length - 1; i++) {
            maxIndex = i;
            // 최대값의 index 를 찾음
            for (int j = i + 1; j < array.length; j++) {

                if (array[maxIndex] < array[j]) {
                    maxIndex = j;
                }
            }
            // 최대값을 임시저장
            temp = array[maxIndex];
            // 기존 최대값 자리에 i 번째 요소를 넣음 -> 최대값이 array 에서 삭제되는 효과 
            array[maxIndex] = array[i];
            // 최대값을 array i 번째에 넣음 -> 기존 값과 최대값이 자리를 바꿈 
            array[i] = temp;
        }
    }

    public static void main(String[] args) {

        int[] targetList = {5, 3, 6, 2, 10};
        selectionSort(targetList);

        for (int number : targetList) {
            System.out.println(number);
        }
    }
}