대학과제 c++ 삽입정렬 오름차순 질문입니다ㅜ
콘솔 창처럼 나오게하라는데 잘 모르겠어요..
//코드추가라는 주석문에 코드를 추가하면 된다는데 무슨코드를 추가해야하나요 ??ㅜㅜㅜ 제발 알려주세요 간곡히 부탁드리겠습니다 제발 ㅜㅜ
삽입정렬의 설명은 교제를 찾아 보시길 권합니다.
9,6,8,1,3,2,4
첫번째 + 1 순서에 있는 6 부터 자기 보다 앞에 위치한 숫자가 작은지 판단하여 작으면 본인이 앞으로 이동하고 나머지는 뒤로 밀리는 형태의 정렬 입니다.
6 9 8 1 3 2 4
=> 6이 9보다 작으므로 6은 9의 위치로 가고 9는 한 칸 밀립니다.6 8 9 1 3 2 4
=> 8이 9보다는 작고 6보다는 크니 8이 9의 위치로 가고 9는 한 칸 밀립니다.
1 6 8 9 3 2 4
=> 1이 9보다 작고, 8보다 크고, 6보다 작아서 1이 6의 위치로 갑니다.
=> 1이 원래 있던 자리인 4번째 부터 ~ 1이 이동한 첫번째 전까지 위치해 있던 6,8,9는 한칸씩 뒤로 이동합니다.
1 3 6 8 9 2 4
=> 3은 9보다 작고, 8보다 작고, 6보다 작고, 1보다는 커서 3은 6의 위치로 갑니다.
=> 3이 원래 있던 자리인 5번째 부터 3이 이동한 두번째 전까지 위치해 있던 6,8,9는 한칸씩 뒤로 이동합니다.
1 2 3 6 8 9 4
=> 2는 9, 8, 6, 3보다 작고 1보다는 커서 2는 3의 위치로 갑니다.
=> 2가 원래 있던 자리인 6번째 부터 2가 이동한 두번쨰 전까지 위치해 있던 3,6,8,9는 한칸씩 뒤로 이동합니다.
1 2 3 4 6 8 9
=> 4는 9,8,6보다 작고 3보다는 커서 4는 6의 위치로 갑니다.
=> 4가 원래 있던 자리인 7번째 부터 4가 이동한 네번째 전까지 위치에 했던 6,8,9는 한칸씩 뒤로 이동합니다.
총 6번의 반복을 하면서
위치의 이동이 발생하면 본인과 비교해서 큰 숫자들을 한 칸씩 뒤로 미루며 자신의 자리를 확보해야 하는 코드가 필요 합니다.
temp = arr[i+1]; // 여기서 temp는 각 회차마다 비교 대상이 되는 숫자 입니다. 6 -> 8 -> 1 -> 3 -> 2 -> 4
위치 이동은 if문에서 k = j 로 자기가 갈 위치를 기억하고 있습니다.
arr[k] = temp; // 내가 이동할 k 위치에 내 값을 넣는 겁니다.
그 전에 내가 갈 자리를 확보하기 위해 본래 k 위치에 있는 애들을 한칸씩 뒤로 미룹니다. 어디까지? 내가 있던 자리인 i+1 위치까지요
위 정보를 종합하여 필요한 코드는 아래와 같습니다.
for ( j = i + 1; j > k; j-- ) {
arr[j] = arr[j-1];
}
j는 내가 원래 있던 자리인 i + 1의 위치부터 내가 이동할 k 위치까지 1씩 감소하면서 뒤로 한칸씩 미루는 작업을 합니다.
정렬 과제는 지속적으로 나 올 테니 잘 모르시면 printf를 여러군데 찍어보고 이해를 해보시는게 좋을 것 같습니다.
안녕하세요.
이중포문 돌면서 오름차순 되는 과정을 보시면 이름대로 알맞은 자리에 삽입해주며 정렬되고 있는 것을 보실 수 있네요.
바깥 포문은 경우 이번에 자리를 옮길 숫자(temp)를 정하는 것이라고 보시면 될 것 같고
안쪽 포문은 이번에 자리를 옮길 숫자(temp)의 알맞게 이동할 자리를 찾기위해 처음부터, 이번숫자까지(바깥포문범위까지)만 비교하시는 걸 볼 수 있습니다.
안쪽 포문에서 알맞은 자리를 찾아주고 있기 때문에,
옮길 숫자를 알맞은 자리에 옮겨주고 한칸씩 옮겨줘야 알맞게 삽입정렬이 될 것으로 보입니다.
그리고 arr[k] = temp; 의 경우 마지막으로 원하는자리에 꽂은 것으로 보이기 떄문에 다음과같은 코드가 추가되어야 할 것 같습니다.
for(j=i+1; j>k; j--) { arr[j] = arr[j-1]; }코드가 의미하는 바는, 이번에 자리를 옮길 숫자의 위치부터, 해당 숫자가 이동할 숫자까지를 한칸씩 땡겨주는 것입니다.
그 후에 기존에 있던 arr[k] = temp; 를 통해 이번에 자리를 옮기는 숫자가 이동될 위치로 옮겨집니다.