(d) Few swaps: (b)번 데이터에서 출발하여, int(√n)개의 random number pair (i, j)를 생성하여 i번째
원소와 j번째 원소를 서로 교환함 (이때 |i − j| <√n의 조건을 만족하도록 할 것).
만약 b번에서 생성된 100개의 데이터가 있다면 그 중 10개의 데이터를 선별하여 i, j번째 데이터를 서로 교환한 다음
최종적으로 10개의 데이터를 sort하라는 의미인가요?
(d) Few swaps: (b)번 데이터에서 출발하여, int(√n)개의 random number pair (i, j)를 생성하여 i번째
원소와 j번째 원소를 서로 교환함 (이때 |i − j| <√n의 조건을 만족하도록 할 것).
만약 b번에서 생성된 100개의 데이터가 있다면 그 중 10개의 데이터를 선별하여 i, j번째 데이터를 서로 교환한 다음
최종적으로 10개의 데이터를 sort하라는 의미인가요?
아닙니다. N의 갯수는 동일합니다.
여기서 루트 N개만큼의 데이터 쌍을 뽑아 SWAP을 시킨 데이터를 만들라는 의미입니다.
다만 데이터 쌍들은 루트N보다 가까운 거리의 데이터 쌍을 뽑아야 합니다.