การเรียงลำดับแบบนับ

ระดับ	อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูล	อาร์เรย์
ประสิทธิภาพในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n+k)}$โดยที่ k คือช่วงของค่าคีย์ที่ไม่เป็นลบ
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุด	${\displaystyle O(n+k)}$

ในวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบนับ ( Counting Sort)เป็นอัลกอริทึมสำหรับการเรียงลำดับชุดของวัตถุตามคีย์ที่เป็นจำนวนเต็ม บวกขนาดเล็ก กล่าวคือ เป็น อัลกอริทึม การเรียงลำดับแบบจำนวนเต็มโดยทำงานโดยการนับจำนวนวัตถุที่มีค่าคีย์ที่แตกต่างกัน และใช้ผลรวมนำหน้า (Prefix Sum) กับจำนวนนับเหล่านั้นเพื่อกำหนดตำแหน่งของแต่ละค่าคีย์ในลำดับผลลัพธ์ เวลาในการทำงานของมันเป็นเชิงเส้นตามจำนวนรายการและความแตกต่างระหว่างค่าคีย์สูงสุดและค่าคีย์ต่ำสุด ดังนั้นจึงเหมาะสำหรับการใช้งานโดยตรงในสถานการณ์ที่ความแปรผันของคีย์ไม่มากกว่าจำนวนรายการอย่างมีนัยสำคัญ มักใช้เป็นซับรูทีนในการเรียงลำดับแบบเรเดียน (Radix Sort)ซึ่งเป็นอัลกอริทึมการเรียงลำดับอีกแบบหนึ่งที่สามารถจัดการกับคีย์ขนาดใหญ่ได้อย่างมีประสิทธิภาพมากขึ้น^{[ 1 ] [ 2 ] [ 3 ]}

การเรียงลำดับแบบนับไม่ใช่การเรียงลำดับแบบเปรียบเทียบมันใช้ค่าคีย์เป็นดัชนีในอาร์เรย์ และขอบเขตล่างΩ ( n log n ) สำหรับการเรียงลำดับแบบเปรียบเทียบจะไม่ถูกนำมาใช้^{[ 1 ]}การเรียงลำดับแบบถังอาจใช้แทนการเรียงลำดับแบบนับได้ และเกี่ยวข้องกับการวิเคราะห์เวลาที่คล้ายกัน อย่างไรก็ตาม เมื่อเปรียบเทียบกับการเรียงลำดับแบบนับ การเรียงลำดับแบบถังต้องการรายการเชื่อมโยงอาร์เรย์แบบไดนามิกหรือหน่วยความจำที่จัดสรรไว้ล่วงหน้าจำนวนมากเพื่อเก็บชุดของรายการภายในแต่ละถัง ในขณะที่การเรียงลำดับแบบนับจะเก็บตัวเลขเดียว (จำนวนรายการ) ต่อถัง^{[ 4 ]}

โดยทั่วไปแล้ว อินพุตของลำดับการนับประกอบด้วยชุดของ รายการ nรายการ โดยแต่ละรายการมีคีย์จำนวนเต็มที่ไม่เป็นลบซึ่งมีค่าสูงสุดไม่เกินk ^{[ 3 ]} ในคำอธิบายบางส่วนของลำดับการนับ อินพุตที่จะเรียงลำดับนั้นถือว่าเป็นเพียงลำดับของจำนวนเต็ม^{[ 1 ]}แต่การทำให้ง่ายขึ้นนี้ไม่สามารถรองรับการใช้งานหลายอย่างของลำดับการนับได้ ตัวอย่างเช่น เมื่อใช้เป็นรูทีนย่อยในลำดับเรเดียน คีย์สำหรับการเรียกใช้ลำดับการนับแต่ละครั้งจะเป็นตัวเลขแต่ละหลักของคีย์รายการที่ใหญ่กว่า การส่งคืนเฉพาะรายการที่เรียงลำดับของตัวเลขคีย์ที่แยกออกจากรายการจะไม่เพียงพอ

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

ผลลัพธ์คืออาร์เรย์ขององค์ประกอบที่เรียงลำดับตามคีย์ เนื่องจากการประยุกต์ใช้กับการเรียงลำดับแบบฐาน การเรียงลำดับแบบนับจึงต้องเป็นการเรียงลำดับแบบเสถียรกล่าวคือ หากองค์ประกอบสองตัวมีคีย์เดียวกัน ลำดับสัมพัทธ์ในอาร์เรย์ผลลัพธ์และลำดับสัมพัทธ์ในอาร์เรย์อินพุตจะต้องตรงกัน^{[ 1 ] [ 2 ]}

สามารถแสดงอัลกอริทึมนี้ในรูปแบบรหัสเทียมได้ดังนี้:

ฟังก์ชัน CountingSort(input, k ) คือ นับ ← อาร์เรย์ของ ศูนย์ k + 1 ตัว เอาต์พุต ← อาร์เรย์ที่มีความยาวเท่ากับอินพุต สำหรับiตั้งแต่ 0 ถึงความยาวของอินพุต - 1 ให้j = คีย์ของอินพุต[ i ] count[ j ] = count[ j ] + 1 สำหรับi = 1 ถึงk ให้คำนวณ count[ i ] = count[ i ] + count[ i - 1] สำหรับi = ความยาวของอินพุต - 1 ลงไปจนถึง 0 ให้j = คีย์ของอินพุต[ i ] count[ j ] = count[ j ] - 1 output[count[ j ]] = input[ i ] ส่งคืนผลลัพธ์ 

inputอาร์เรย์ที่จะเรียงลำดับอยู่ที่ไหน จะ keyส่งคืนค่าตัวเลขของแต่ละรายการในอาร์เรย์อินพุตcountเป็นอาร์เรย์เสริมที่ใช้เก็บจำนวนรายการที่มีแต่ละคีย์ก่อน จากนั้น (หลังจากลูปที่สอง) จะใช้เก็บตำแหน่งที่ควรวางรายการที่มีแต่ละคีย์ kเป็นค่าสูงสุดของค่าคีย์ที่ไม่เป็นลบ และoutputเป็นอาร์เรย์เอาต์พุตที่เรียงลำดับแล้ว

โดยสรุป อัลกอริทึมจะวนซ้ำรายการในลูปแรก โดยคำนวณฮิสโตแกรมของจำนวนครั้งที่แต่ละคีย์ปรากฏในinputคอลเลกชัน หลังจากนั้นในลูปที่สอง จะทำการคำนวณผลรวมนำหน้าcountเพื่อกำหนดช่วงตำแหน่งที่ควรวางรายการที่มีคีย์นั้นสำหรับแต่ละคีย์ กล่าวคือ รายการที่มีคีย์ควรวางเริ่มต้นที่ตำแหน่งสุดท้าย ในลูปที่สาม จะวนซ้ำรายการอีกครั้ง แต่ในลำดับย้อนกลับ โดยย้ายแต่ละรายการไปยังตำแหน่งที่เรียงลำดับแล้วในอาร์เรย์^{[ 1 ] [ 2 ] [ 3 ]}${\displaystyle i}$count[${\displaystyle i}$]inputoutput

ลำดับสัมพัทธ์ของรายการที่มีคีย์เท่ากันจะถูกรักษาไว้ในที่นี้ กล่าวคือ นี่คือ การเรียงลำดับ แบบ เสถียร

เนื่องจากอัลกอริทึมใช้เพียงforลูปแบบง่ายๆ โดยไม่มีการเรียกซ้ำหรือการเรียกซับรูทีน จึงสามารถวิเคราะห์ได้อย่างง่ายดาย การเริ่มต้นอาร์เรย์นับ และลูป for ตัวที่สองซึ่งทำการบวกแบบพรีฟิกบนอาร์เรย์นับ แต่ละลูปจะวนซ้ำอย่างมากที่สุดk + 1ครั้ง ดังนั้นจึงใช้ เวลา O ( k )ลูป for อีกสองลูป และการเริ่มต้นอาร์เรย์เอาต์พุต แต่ละลูปใช้ เวลา O ( n )ดังนั้น เวลาสำหรับอัลกอริทึมทั้งหมดคือผลรวมของเวลาสำหรับขั้นตอนเหล่านี้O ( n + k ) ^{[ 1 ] [ 2 ]}

เนื่องจากใช้อาร์เรย์ที่มีความยาวk + 1และnพื้นที่ใช้งานทั้งหมดของอัลกอริทึมจึงเป็น O ( n + k ) เช่นกัน[ 1 ] สำหรับกรณีปัญหาที่^{ค่าคีย์สูงสุด}มีขนาดเล็กกว่าจำนวนรายการอย่างมาก การเรียงลำดับแบบนับสามารถมีประสิทธิภาพด้านพื้นที่สูง เนื่องจากพื้นที่จัดเก็บเพียงอย่างเดียวที่ใช้ นอกเหนือจากอาร์เรย์อินพุตและเอาต์พุต คือ อาร์เรย์ Count ซึ่งใช้พื้นที่O ( k ) ^{[ 5 ]}

หากแต่ละรายการที่จะเรียงลำดับเป็นจำนวนเต็ม และใช้เป็นคีย์ด้วยเช่นกัน ลูปที่สองและสามของการเรียงลำดับแบบนับสามารถรวมเข้าด้วยกันได้ โดยในลูปที่สอง แทนที่จะคำนวณตำแหน่งที่iควรวางรายการที่มีคีย์ในผลลัพธ์ ให้เพิ่มCount[i]สำเนาของตัวเลขนั้นiลงในผลลัพธ์ แทน

อัลกอริทึมนี้ยังสามารถใช้เพื่อกำจัดคีย์ที่ซ้ำกันได้ โดยการแทนที่Countอาร์เรย์ด้วยเวกเตอร์บิตที่เก็บค่าoneสำหรับคีย์ที่มีอยู่ในข้อมูลป้อนเข้า และค่าzeroสำหรับคีย์ที่ไม่มีอยู่ หากรายการเหล่านั้นเป็นคีย์จำนวนเต็มเอง ก็สามารถละเว้นลูปที่สองและสามได้ทั้งหมด และเวกเตอร์บิตจะทำหน้าที่เป็นเอาต์พุต โดยแสดงค่าเป็นค่าชดเชยของzeroรายการที่ไม่มีอยู่ บวกกับค่าต่ำสุดของช่วง ดังนั้นคีย์จะถูกจัดเรียงและคีย์ที่ซ้ำกันจะถูกกำจัดในเวอร์ชันนี้เพียงแค่ใส่ลงในอาร์เรย์บิต

สำหรับข้อมูลที่ขนาดคีย์สูงสุดมีขนาดเล็กกว่าจำนวนรายการข้อมูลอย่างมาก การเรียงลำดับแบบนับอาจทำงานแบบขนานได้โดยการแบ่งอินพุตออกเป็นอาร์เรย์ย่อยที่มีขนาดใกล้เคียงกัน ประมวลผลแต่ละอาร์เรย์ย่อยแบบขนานเพื่อสร้างอาร์เรย์นับแยกต่างหากสำหรับแต่ละอาร์เรย์ย่อย จากนั้นจึงรวมอาร์เรย์นับเข้าด้วยกัน เมื่อใช้เป็นส่วนหนึ่งของอัลกอริทึมการเรียงลำดับแบบฐานขนาน ควรเลือกขนาดคีย์ (ฐานของการแสดงฐาน) ให้ตรงกับขนาดของอาร์เรย์ย่อยที่แบ่ง^{[ 6 ]}ความเรียบง่ายของอัลกอริทึมการเรียงลำดับแบบนับและการใช้พรีฟิกผลรวมแบบขนานที่ง่ายต่อการทำงานแบบขนานยังทำให้สามารถใช้งานได้ในอัลกอริทึมแบบขนานที่มีความละเอียดสูงกว่า^{[ 7 ]}

ตามที่อธิบายไว้ การเรียงลำดับแบบนับไม่ใช่ขั้นตอนวิธีแบบ in-placeแม้จะไม่คำนึงถึงอาร์เรย์นับ ก็ยังต้องการอาร์เรย์อินพุตและเอาต์พุตแยกต่างหาก เป็นไปได้ที่จะปรับเปลี่ยนขั้นตอนวิธีเพื่อให้วางรายการลงในลำดับที่เรียงแล้วภายในอาร์เรย์เดียวกันกับที่ให้เป็นอินพุต โดยใช้อาร์เรย์นับเป็นเพียงที่เก็บข้อมูลเสริม อย่างไรก็ตาม เวอร์ชัน in-place ที่ปรับเปลี่ยนของการเรียงลำดับแบบนับนั้นไม่เสถียร^{[ 3 ]}

แม้ว่าการเรียงลำดับแบบฐานจะมีมานานกว่านั้นมาก แต่การเรียงลำดับแบบนับและการประยุกต์ใช้กับการเรียงลำดับแบบฐานนั้นถูกคิดค้นโดยHarold H. Sewardในปี พ.ศ. 2497 ^{[ 1 ] [ 4 ] [ 8 ]}

ใน Wikibook Algorithm implementationมีหน้าหนึ่งที่กล่าวถึงหัวข้อ: การเรียงลำดับแบบนับ (Counting sort)

• การแสดงผลแบบเรียงลำดับนับด้วย HTML5
• แอปเพล็ตสาธิตจากมหาวิทยาลัยคาร์ดิฟฟ์ เก็บถาวรเมื่อวันที่ 2 มิถุนายน 2013 ที่Wayback Machine
• Kagel, Art S. (2 มิถุนายน 2549), "counting sort", ใน Black, Paul E. (บรรณาธิการ), Dictionary of Algorithms and Data Structures , US National Institute of Standards and Technology , สืบค้นเมื่อ 21 เมษายน 2554.