삽입 정렬 알고리즘은 정렬되지 않은 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 하나씩 가져와 정렬된 부분에 삽입하여 정렬하는 방식으로 동작한다.
첫 번째 요소만이 정렬된 부분이고, 나머지 요소들은 정렬되지 않은 부분으로 정렬되지 않은 부분에서 하나의 요소를 선택하여 정렬된 부분에 삽입한다. 선택된 요소를 적절한 위치에 삽입하기 위해 정렬된 부분을 순회하면서 삽입할 위치를 찾으며 정렬되지 않은 부분이 모두 정렬된 상태가 될 때까지 위의 과정을 반복한다.
삽입 정렬의 시간 복잡도는 최선의 경우 O(n), 평균 및 최악의 경우 O(n^2)이다. 대량의 데이터를 정렬하는데는 효율적이지 않지만, 데이터가 이미 거의 정렬된 상태이거나 작은 크기의 데이터를 정렬할 때는 유용할 수 있다.
accept p_num prompt '정렬할 5개 숫자 입력 :'
-- 배열 선언
declare
type array_t is varray(100) of number(10);
varray array_t := array_t();
v_temp number(10);
--입력 숫자를 varray 에 저장
begin
varray.extend(regexp_count('&p_num', ' ')+1);
--VARRAY(가변 배열)를 사용하여 배열의 크기를 확장한다.
--regexp_count(&p_num , )는 주어진 문자열(&p_num)에서 정규 표현식 패턴에 매치되는 부분의 개수를 반환하는 함수
--&p_num에서 정규 표현식 패턴에 매치되는 부분의 개수에 1을 더한 값이 VARRAY의 새로운 크기로 사용된다.
for i in 1 .. varray.count loop
varray(i) := to_number(regexp_substr('&p_num', '[^ ]+', 1, i));
end loop;
--문자열(&p_num)에서 공백을 기준으로 i번째로 나타나는 부분 문자열을 반환합니다. `[^ ]+`는 공백이 아닌 문자열을 의미
--공백을 기준으로 분리된 부분 문자열을 숫자로 변환하여 VARRAY에 저장하는 작업을 반복.
--삽입 정렬을 사용하여 varray 정렬
for j in 2 .. varray.count loop
for k in 1 .. j-1 loop
if varray(k)>varray(j) then
v_temp :=varray(j);
for z in reverse k .. j-1 loop
varray(z+1) := varray(z);
end loop;
varray(k) :=v_temp;
end if;
end loop;
end loop;
--정렬 결과출력
for i in 1 .. varray.count loop
dbms_output.put(varray(i) || ' ');
end loop;
dbms_output.new_line;
end;
/
입력된 숫자들의 개수에 따라 배열 크기를 동적으로 확장한다.
&p_num은 사용자로부터 입력받은 문자열을 나타낸다. regexp_count 함수는 입력된 숫자의 개수를 세고, 이를 기반으로 배열 크기를 설정한다.
입력된 문자열에서 공백( )의 개수를 계산하여 입력된 숫자의 개수를 알 수 있고 패턴의 개수를 반환한다.
입력된 숫자들을 배열에 할당
for k in 1 .. j-1 loop: 안쪽 반복문에서는 현재 요소와 그 이전 요소를 비교한다.
varray(k) > varray(j) then: 만약 현재 요소가 다음 요소보다 크다면 실행된다.
v_temp := varray(j) ;: 임시 변수에 다음 요소의 값을 저장한다.
for z in reverse k .. j-1 loop: 현재 요소의 위치를 결정하기 위해 배열을 이동시킨다. 이 반복문은 현재 요소부터 다음 요소 직전까지 거꾸로 진행된다.
