อัลกอริทึมการเรียงลำดับ Radix ในโครงสร้างข้อมูล

อัลกอริทึมการเรียงลำดับ Radix คืออะไร

Radix Sort เป็นอัลกอริธึมการเรียงลำดับแบบไม่เปรียบเทียบ มันทำงานโดยการจัดกลุ่มตัวเลขแต่ละตัวขององค์ประกอบที่จะเรียงลำดับ จากนั้นจะใช้เทคนิคการเรียงลำดับที่มีความเสถียรเพื่อจัดระเบียบองค์ประกอบตามฐานของมัน มันเป็นอัลกอริธึมการเรียงลำดับเชิงเส้น

กระบวนการเรียงลำดับเกี่ยวข้องกับคุณสมบัติต่อไปนี้:

• การค้นหาองค์ประกอบสูงสุดและรับจำนวนหลักขององค์ประกอบนั้น มันบอกจำนวนการวนซ้ำที่กระบวนการเรียงลำดับจะตามมา
• จัดกลุ่มตัวเลขแต่ละตัวขององค์ประกอบในตำแหน่งที่มีนัยสำคัญเท่ากันในการวนซ้ำแต่ละครั้ง
• กระบวนการจัดกลุ่มจะเริ่มจากหลักที่มีนัยสำคัญน้อยที่สุดและสิ้นสุดที่หลักที่มีนัยสำคัญที่สุด
• การเรียงลำดับองค์ประกอบตามตัวเลขในตำแหน่งสำคัญนั้น
• การรักษาลำดับสัมพัทธ์ขององค์ประกอบที่มีค่าคีย์เดียวกัน คุณสมบัติของการเรียงลำดับ Radix นี้จะทำให้การเรียงลำดับมีความเสถียร

การวนซ้ำครั้งสุดท้ายจะทำให้เราได้รับรายการที่จัดเรียงอย่างสมบูรณ์

การทำงานของอัลกอริทึมการเรียงลำดับ Radix

ลองเรียงลำดับรายการจำนวนเต็มในรูปด้านบนตามลำดับจากน้อยไปมากโดยใช้อัลกอริทึม Radix Sort

ต่อไปนี้เป็นขั้นตอนในการดำเนินการกระบวนการเรียงลำดับ Radix:

ขั้นตอน 1) ระบุองค์ประกอบที่มีค่าสูงสุดในรายการ ในกรณีนี้คือ 835

ขั้นตอน 2) คำนวณจำนวนหลักขององค์ประกอบสูงสุด 835 มี 3 หลักพอดี

ขั้นตอน 3) กำหนดจำนวนการวนซ้ำตามขั้นตอนที่ 2 835 มีตัวเลข 3 หลัก หมายความว่าจำนวนการวนซ้ำจะเป็น 3

ขั้นตอน 4) กำหนดฐานขององค์ประกอบ เนื่องจากเป็นระบบทศนิยม ฐานจึงเป็น 10

ขั้นตอน 5) เริ่มการทำซ้ำครั้งแรก

ก) การทำซ้ำครั้งแรก

ในการวนซ้ำครั้งแรก เราจะพิจารณาค่าตำแหน่งหน่วยของแต่ละองค์ประกอบ

ขั้นตอน 1) แก้ไขจำนวนเต็มด้วย 10 เพื่อให้ได้หน่วยตำแหน่งขององค์ประกอบ ตัวอย่างเช่น 623 mod 10 ให้ค่า 3 แก่เรา และ 248 mod 10 ให้ค่า 8 แก่เรา

ขั้นตอน 2) ใช้การเรียงลำดับการนับหรือการเรียงลำดับแบบคงที่อื่นๆ เพื่อจัดระเบียบจำนวนเต็มตามหลักที่มีนัยสำคัญน้อยที่สุด เท่าที่เห็น จากรูป 248 จะตกถังที่ 8 623 จะตกถังที่ 3 ไปเรื่อยๆ

หลังจากการวนซ้ำครั้งแรก ตอนนี้รายการจะเป็นดังนี้

ดังที่คุณเห็นจากรูปด้านบน รายการยังไม่ได้เรียงลำดับ และต้องมีการวนซ้ำมากขึ้นจึงจะจัดเรียงได้ครบถ้วน

b) การทำซ้ำครั้งที่สอง

ในการวนซ้ำนี้ เราจะพิจารณาเลขหลักที่ 10^th สถานที่สำหรับกระบวนการคัดแยก

ขั้นตอน 1) หารจำนวนเต็มด้วย 10 248 หารด้วย 10 จะได้ 24

ขั้นตอน 2) แก้ไขเอาต์พุตของขั้นตอนที่ 1 ด้วย 10 24 mod 10 ให้ 4

ขั้นตอน 3) ทำตามขั้นตอนที่ 2 จากการทำซ้ำครั้งก่อน

หลังจากทำซ้ำครั้งที่สอง รายการจะเป็นดังนี้

จากรูปด้านบนจะเห็นได้ว่ารายการยังเรียงลำดับไม่หมดเนื่องจากยังไม่เรียงลำดับจากน้อยไปมาก

c) การทำซ้ำครั้งที่สาม

สำหรับการวนซ้ำครั้งสุดท้าย เราต้องการได้หลักที่มีนัยสำคัญที่สุด ในกรณีนี้คือ 100^th ตำแหน่งสำหรับจำนวนเต็มแต่ละตัวในรายการ

ขั้นตอน 1) หารจำนวนเต็มด้วย 100… 415 หารด้วย 100 จะได้ 4

ขั้นตอน 2) แก้ไขผลลัพธ์จากขั้นตอนที่ 1 ด้วย 10 4 mod 10 ให้ 4 อีกครั้ง

ขั้นตอน 3) ทำตามขั้นตอนที่ 3 จากการทำซ้ำครั้งก่อน

ดังที่เราเห็น รายการจะเรียงลำดับจากน้อยไปหามาก การวนซ้ำครั้งสุดท้ายเสร็จสิ้นแล้ว และกระบวนการจัดเรียงก็เสร็จสิ้นแล้ว

รหัสเทียมของอัลกอริทึมการเรียงลำดับ Radix

นี่คือรหัสหลอกสำหรับอัลกอริทึมการเรียงลำดับ Radix

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the jth place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace
   arr = sorted elements

C++ โปรแกรมเพื่อใช้งาน Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Output:

162 248 415 623 835

Python โปรแกรมสำหรับอัลกอริทึมการเรียงลำดับ Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Output:

[162,248,415,623,835]

การวิเคราะห์ความซับซ้อนของการเรียงลำดับแบบ Radix

ความซับซ้อนมีสองประเภทที่ต้องพิจารณา คือ ความซับซ้อนของพื้นที่และความซับซ้อนของเวลา

• ความซับซ้อนของพื้นที่: O(n+b) โดยที่ n คือขนาดของอาร์เรย์และ b คือฐานที่พิจารณา
• ความซับซ้อนของเวลา: O(d*(n+b)) โดยที่ d คือจำนวนหลักขององค์ประกอบที่ใหญ่ที่สุดในอาร์เรย์

ความซับซ้อนของพื้นที่ของการเรียงลำดับแบบเรดิกซ์

สองคุณสมบัติที่ต้องเน้นสำหรับความซับซ้อนของพื้นที่

• จำนวนองค์ประกอบในอาร์เรย์ n.
• ฐานสำหรับแสดงองค์ประกอบ b.

บางครั้งฐานนี้อาจใหญ่กว่าขนาดของอาร์เรย์ได้

ความซับซ้อนโดยรวมจึงเป็น O(n+b)

คุณสมบัติต่อไปนี้ขององค์ประกอบในรายการสามารถทำให้พื้นที่การเรียงลำดับแบบเรดิกซ์ไม่มีประสิทธิภาพ:

• องค์ประกอบที่มีตัวเลขจำนวนมาก
• ฐานขององค์ประกอบมีขนาดใหญ่ เช่น ตัวเลข 64 บิต

ความซับซ้อนของเวลาของการเรียงลำดับแบบเรดิกซ์

คุณสามารถใช้การเรียงลำดับการนับเป็นรูทีนย่อยได้ เนื่องจากการวนซ้ำแต่ละครั้งจะต้องใช้เวลาอีโอ(n+b) เวลา. หากมีการวนซ้ำ เวลาทำงานทั้งหมดจะกลายเป็น O(ง*(n+b)) ที่นี่ “O” หมายถึงฟังก์ชันความซับซ้อน

ความเป็นเชิงเส้นของการเรียงลำดับ Radix

Radix Sort จะเป็นเส้นตรงเมื่อ

• d เป็นค่าคงที่ โดยที่ d คือจำนวนหลักขององค์ประกอบที่ใหญ่ที่สุด
• b ก็ไม่ใหญ่โตนักเมื่อเทียบกับ n.

การเปรียบเทียบ Radix Sort กับอัลกอริธึมการเปรียบเทียบอื่น ๆ

ดังที่เราได้เห็น ความซับซ้อนของการเรียงลำดับแบบ Radix นั้นขึ้นอยู่กับขนาดของคำหรือตัวเลข การเรียงลำดับแบบ Radix จะมีความซับซ้อนเท่ากันสำหรับกรณีเฉลี่ยและกรณีที่ดีที่สุด ซึ่งก็คือ O(d*(n+b)) นอกจากนี้ ยังแตกต่างกันไปตามเทคนิคการเรียงลำดับที่คุณใช้ตรงกลาง ตัวอย่างเช่น คุณสามารถใช้การเรียงลำดับแบบนับหรือการเรียงลำดับด่วนสำหรับอัลกอริทึมการเรียงลำดับระดับกลางภายในการเรียงลำดับแบบ Radix

การประยุกต์ใช้อัลกอริทึมการเรียงลำดับ Radix

การใช้งานที่สำคัญของ Radix Sort คือ:

• Radix Sort สามารถใช้เป็นอัลกอริธึมการค้นหาตำแหน่งที่ใช้ช่วงค่าจำนวนมาก
• ใช้ในการสร้างอาร์เรย์ต่อท้ายในอัลกอริทึม DC3
• ใช้ในเครื่องคอมพิวเตอร์ทั่วไปที่มีการเข้าถึงแบบสุ่มต่อเนื่องซึ่งใช้การป้อนข้อมูลแบบคีย์