Algorithm1 Homework4

4 종류의 radix sort를 구현한다.

과제 내용

• Radix sort는 정렬에 사용할 자릿수의 방향에 따라 LSD와 MSD로 나뉘며, 데이터가 저장된 리스트에 대한 연산 방식에 따라 list와 array로 나눌 수 있다. Array 방식은 리스트를 사용하기가 불편한 C와 같은 프로그래밍 언어에서 사용하기 적합한 방식이며, list 방식은 파이썬에서 사용하기에 적합하다.
• Radix sort의 자리수 방향 2 종류와 리스트의 연산 방식 2 종류를 결합하면 모두 4 종류의 radix sort가 아래와 같이 존재한다.
  • LSD_list(list)
    • for-문을 사용한다면 element in list와 같이 list내의 element에 대해 동작을 수행한다.
    • list.append(value)와 같이 list의 끝에 element를 붙이는 list관련 method를 사용한다.
    • list[i]와 같이 index를 통해 list의 element에 접근하지 않도록 한다.
  • LSD_array(array)
    • for-문을 사용한다면 i in range(len(list))와 같이 인덱스를 기반으로 동작을 수행한다.
    • list[i]와 같이 인덱스로 표시된 리스트 내의 element 값을 읽거나 변경한다.
    • list 관련 method는 사용하지 않는다. 다만 list[:4] 같은 리스트 슬라이싱 (slicing)이나 [x for x in list] 같은 리스트 컴프리헨션 (comprehension)은 사용가능하다.
  • MSD_list(list)
    • 위에서 언급한 리스트 관련 연산을 사용하며 배열 관련 연산을 피한다.
  • MSD_array(array)
    • 위에서 언급한 배열 관련 연산을 사용하며 리스트 관련 연산/메소드를 피한다.
• 위의 네 함수들은 리스트를 입력으로 받아 정렬된 리스트를 반환한다.
• 이 함수를 구현할 때 chatGPT같은 LLM을 적극적으로 사용한다. 특히, 퍼플렉시티 프로 버전이 학교 이메일을 가진 학생 대상으로 1년 무료 행사를 진행하고 있으니 이를 이용하는 것도 좋다. (네이버 웍스 게시판 참고)
• 테스트로 사용되는 파일은 data10.txt, data1000.txt, data1M.txt가 정렬되지 않은 양의 정수가 있는 기본 텍스트 파일이며, 파일명의 끝에 a가 붙은 것은 정수 10000000000000가 추가된 것이다. 이 정수는 radix sort의 실행 시간을 늘이는 역할을 한다.

과제 평가

• 완성된 프로그램의 평가는 다음 명령어들로 이루어진다. 대괄호 안의 첫 번째 인자는 4 종류 중 어떤 radix sort를 호출할 것인지 결정하며, 하이픈 다음의 두 번째 인자는 입력 파일을 가리킨다. 제대로 실행될 경우 passed가 출력되고, 실패할 경우 failed가 출력된다.

  pytest test_radixSort.py -k "test_rs[LSD_list-data10.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data10.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data10.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data10.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_list-data10a.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data10a.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data10a.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data10a.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_list-data1000.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data1000.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data1000.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data1000.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_list-data1000a.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data1000a.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data1000a.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data1000a.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_list-data1M.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data1M.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data1M.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data1M.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_list-data1Ma.txt]"

  pytest test_radixSort.py -k "test_rs[LSD_array-data1Ma.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_list-data1Ma.txt]"

  pytest test_radixSort.py -k "test_rs[MSD_array-data1Ma.txt]"