삽입정렬 Insertion sort 에 대해 발표하려고 준비하다가 chatgpt 를 사용해보았다
처음에 배열기반 삽입정렬이 링크드리스트 기반 삽입정렬보다 느릴거라고 생각하였다
왜냐면 특정 원소를 뺄때 그 원소의 뒤에있는 원소들이 앞으로 땡겨지고
삽일할때 그 원소뒤로 원소들이 뒤로 밀려지니까 느려질거라고 생각하였다
이동할 A와 이동할 위치까지 사이의 값들을 한칸씩 뒤로 미는 과정이 필요하다
반면에 링크드리스트는 삽입과 삭제가 빠르고 노드간에 참조만 수정하면 되는 거니까 라고 생각함
근데 왠걸 배열기반이 훨씬 빠르다..
왜 삽입정렬 구현에서 LinkedList 가 ArrayList 보다 느린걸까 물어봤다
LinkedList 에서 원소접근할때 시간이 오래걸린다고 한다
LinkedList<Integer>를 사용한 삽입 정렬은 기본 데이터 구조와
정렬에 필요한 작업의 차이로 인해 ArrayList<Integer>를 사용하는
것보다 느립니다.
ArrayList에서 요소는 인덱스를 기반으로 요소에 대한 빠른 임의 액세스를
제공하는 연속 메모리 블록에 저장됩니다. 이를 통해 삽입 정렬 알고리즘은
정렬 프로세스 중에 요소에 빠르게 액세스하고 요소를 조작할 수 있습니다.
반면에 LinkedList는 각각 데이터 요소와 다음 노드에 대한 참조를
포함하는 일련의 노드로 구성됩니다. 즉, 목록을 처음부터 원하는
인덱스까지 순회해야 하므로 요소에 대한 임의 액세스가 더 느립니다.
또한 LinkedList의 요소를 조작하려면 노드 간의 참조를 변경해야 하며
이는 ArrayList의 요소를 복사하는 것보다 느릴 수 있습니다.
따라서 LinkedList<Integer>를 사용한 삽입 정렬은 ArrayList<Integer>를
사용한 것보다 더 많은 연산이 필요하고 시간이 오래 걸린다. 그러나
LinkedList는 노드 간의 참조 업데이트만 필요한 구조로 인해 목록
중간에서 요소를 추가하거나 제거하는 것과 같은 특정 작업의 경우
ArrayList보다 빠를 수 있으며 ArrayList는 새 요소를 위한 공간을
만들기 위해 요소를 이동해야 할 수 있습니다. 또는 요소를 삭제합니다.
일반적으로 ArrayList와 LinkedList 중에서 선택하는 것은 특정
사용 사례와 컬렉션에서 수행될 작업 유형에 따라 다릅니다.그리고 삽입정렬알고리즘을 다시 생각해보니 위치를 바꿀 대상의 A을 백업해두고
앞에있는 숫자들이 A보다 크면 한칸씩 뒤로 밀고
작으면 멈추고 작은대상의 인덱스 + 1 의 위치에 A를 덮어씌우면 된다
삽입정렬 구현에 가장 좋은 자바 컬렉션은 뭐야라고 물어보았다
ArrayList 라고 한다 근데 질문이 잘못되었다 애초에 자바 컬렉션을 사용할 필요가 없다
그냥 배열을 삽입정렬하는게 제일 빠르다.
100000개 랜덤숫자를 ArrayList와 int배열로 삽입정렬해서 시간 비교해봤는데
ArrayList 4초
int배열 0초
걸렸다
Java ArrayList 컬렉션은 삽입 정렬을 구현하는 데 적합합니다. 이는 ArrayList가
삽입 정렬에 필요한 핵심 작업인 임의의 위치에 있는 요소에 대한 효율적인 삽입 및
액세스를 제공하기 때문입니다.
삽입 정렬은 배열의 각 요소를 정렬된 하위 배열의 올바른 위치에 반복적으로 삽입하여
작동합니다. 새 요소가 삽입될 때마다 정렬된 하위 배열의 크기가 하나씩 커집니다.
ArrayList 컬렉션은 요소가 추가됨에 따라 정렬된 하위 배열을 동적으로 확장하는
편리한 방법을 제공합니다.삽입정렬 속도를 개선할 수 있는 방법을 물어봤다
질문을 서투른 영어로(개떡같이 물어봐도 찰떡같이 답을한다) 막써도 알아서 알아듣고 대답을 잘해준다;;
삽입 위치에 대한 이진 검색: 정렬된 하위 배열의 각 요소와 키를 하나씩 비교하는
대신 이진 검색을 사용하여 삽입 위치를 더 빨리 찾을 수 있습니다. 이렇게 하면
특히 큰 어레이의 경우 필요한 비교 횟수를 크게 줄일 수 있습니다.
한 번에 여러 요소 이동: 각 요소를 한 위치 오른쪽으로 이동하는 대신 키보다 큰
경우 여러 요소를 한 번에 이동할 수 있습니다. 이렇게 하면 필요한 배열 할당 수를
줄이고 알고리즘을 더 빠르게 만들 수 있습니다.
감시 값 사용: 배열의 시작 부분에 감시 값을 추가하면 루프 내부에서 경계 조건
j >= 0을 확인할 필요가 없습니다. 이것은 약간의 오버헤드를 절약하고 알고리즘을
약간 더 빠르게 만들 수 있습니다.그리고 테스트를 해보았다
100만개 34초 걸리던게
개선된 삽입정렬으로는 14초 걸린다 두배가까이 빨라졌다
요약
1. 삽입정렬은 배열을 사용하자.
2. Swap 할 필요없다 정렬대상인 A를 백업하고 A보다 앞에 있는 녀석들중에 A보다 큰녀석들만 한칸씩 밀고 A 보다 작은녀석을 만나면 그 녀석 +1 의 위치에 A를 덮어씌운다
3. A 보다 작은녀석을 찾는데 이진탐색을 사용하면 드라마틱하게 빠르게 개선할 수 있다
