บทความนี้เป็นบทความโดดเดี่ยวเนื่องจากไม่มีบทความอื่นเชื่อมโยงถึงโปรดเพิ่มลิงก์ไปยังหน้านี้จากบทความที่เกี่ยวข้อง( ตุลาคม 2021 )

ในวิทยาการคอมพิวเตอร์ลำดับที่เกือบเรียงลำดับแล้วหรือที่รู้จักกันในชื่อลำดับที่เรียงลำดับอย่างคร่าวๆหรือลำดับที่เรียงลำดับแบบ χ คือลำดับที่เกือบจะเรียงลำดับแล้ว คำว่า เกือบเรียงลำดับแล้ว หมายความว่า ไม่มีองค์ประกอบใดในลำดับที่อยู่ห่างไกลจากตำแหน่งที่ควรจะเป็นหากลำดับนั้นเรียงลำดับอย่างสมบูรณ์ อย่างไรก็ตาม ยังคงมีความเป็นไปได้ที่ไม่มีองค์ประกอบใดในลำดับอยู่ที่ตำแหน่งที่ควรจะเป็นหากลำดับนั้นเรียงลำดับอย่างสมบูรณ์ ${\displaystyle k}$

${\displaystyle k}$การเรียงลำดับแบบ t-sortingคือการจัดเรียงองค์ประกอบของลำดับใหม่เพื่อให้ลำดับนั้นกลายเป็นลำดับแบบ t-sorted การเรียงลำดับแบบ t-sorting โดยทั่วไปมีประสิทธิภาพมากกว่าการเรียงลำดับแบบ t-sorting ในทำนองเดียวกัน การเรียงลำดับลำดับจะง่ายขึ้นหากทราบว่าลำดับนั้นเป็นลำดับแบบt-sorted ดังนั้น หากโปรแกรมต้องการพิจารณาเฉพาะลำดับแบบ t-sorted เป็นอินพุตหรือเอาต์พุต การพิจารณาลำดับแบบ t-sorted อาจช่วยประหยัดเวลาได้ ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

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

กำหนดให้จำนวนบวก n ลำดับ หนึ่ง เรียกว่าเรียงลำดับแบบ nถ้าสำหรับแต่ละ n และสำหรับแต่ละ n นั่นคือ ลำดับจะต้องเรียงลำดับเฉพาะคู่ขององค์ประกอบที่มีระยะห่างอย่างน้อยn เท่านั้น${\displaystyle k}$${\displaystyle [a_{1},\dots ,a_{n}]}$${\displaystyle k}$${\displaystyle 1\leq i}$${\displaystyle i+k\leq j\leq n}$${\displaystyle a_{i}\leq a_{j}}$${\displaystyle k}$

รัศมีของลำดับที่ระบุด้วย^{[ 1 ]}หรือ^{[ 2 ]}คือค่าที่เล็กที่สุดที่ทำให้ลำดับนั้นเรียงลำดับ รัศมีเป็นการวัดการเรียงลำดับล่วงหน้า ${\displaystyle \alpha }$${\displaystyle {\text{ROUGH}}(\alpha )}$${\displaystyle {\text{พาร์}}(\อัลฟา )}$${\displaystyle k}$${\displaystyle k}$

กล่าวได้ว่าลำดับเกือบเรียงแล้วหรือเรียงแล้วโดยประมาณหากรัศมีของลำดับนั้นเล็กเมื่อเทียบกับความยาวของลำดับ

ลำดับจะเรียงลำดับตาม -sorted ก็ต่อเมื่อช่วงแต่ละช่วงที่มีความยาว n นั้นเรียงลำดับตาม -sorted แล้ว ${\displaystyle [a_{1},\dots ,a_{n}]}$${\displaystyle k}$${\displaystyle 2k+2}$${\displaystyle [a_{i},a_{i+1},\dots ,a_{i+2k+2}]}$${\displaystyle k}$

ลำดับทั้งหมดที่มีความยาวจะถูกเรียงลำดับแบบ นั่นคือลำดับจะถูกเรียงลำดับแบบ ก็ต่อเมื่อมันถูกเรียงลำดับแบบ เท่านั้นลำดับที่ถูกเรียงลำดับแบบ จะถูกเรียงลำดับแบบ โดยอัตโนมัติแต่ไม่จำเป็นต้องถูกเรียงลำดับแบบ ด้วย ${\displaystyle n}$${\displaystyle (n-1)}$${\displaystyle 0\leq {\text{Par}}([a_{1},\dots ,a_{n}])<n}$${\displaystyle 0}$${\displaystyle k}$${\displaystyle (k+1)}$${\displaystyle (k-1)}$

กำหนดให้ลำดับ a เป็นลำดับที่เรียงลำดับแล้วและการเรียงสับเปลี่ยนที่เรียงลำดับแล้วของลำดับ a นั้นจะมีค่าไม่เกิน ${\displaystyle k}$${\displaystyle [a_{1},\dots ,a_{n}]}$${\displaystyle [a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]}$${\displaystyle |i-\sigma _{i}|}$${\displaystyle k}$

การตัดสินว่าลำดับใด เรียง ลำดับ ตาม -sorted หรือไม่ สามารถทำได้ในเวลาเชิงเส้นและพื้นที่คงที่โดยใช้อัลกอริธึมแบบสตรีมมิ่งเพียงพอแล้วสำหรับแต่ละค่าของ s ที่จะติดตามค่า s และตรวจสอบว่า s เป็นจริง ${\displaystyle [a_{1},\dots ,a_{n}]}$${\displaystyle k}$${\displaystyle 1\leq i<n-k}$${\displaystyle \max(a_{j}\mid j\leq i)}$${\displaystyle a_{i+k}\geq \max(a_{j}\mid j\leq i)}$

การคำนวณรัศมีของลำดับสามารถทำได้ในเวลาและพื้นที่เชิงเส้น ซึ่งเป็นผลมาจากข้อเท็จจริงที่ว่าสามารถนิยามได้เป็น. ${\displaystyle \max(i-j\mid \min(a_{k}\mid k\geq i)<\max(a_{k}\mid k\leq j))}$

เมื่อกำหนดลำดับที่เรียงลำดับตาม -แล้วจะสามารถคำนวณการเรียงสับเปลี่ยนที่เรียงลำดับตาม - ของ ลำดับนั้นได้ ในเวลาเชิงเส้นและพื้นที่คงที่ ${\displaystyle 2k}$${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$${\displaystyle (k-1)}$${\displaystyle \alpha '}$${\displaystyle \alpha }$

ขั้นแรกสมมติว่าลำดับหนึ่งๆ จะถูกแบ่งออกเป็นส่วนๆ ได้ก็ต่อเมื่อองค์ประกอบที่เล็กกว่า อยู่ในและองค์ประกอบที่ใหญ่กว่า อยู่ใน เราจะเรียกการแบ่งส่วนว่าการเรียงลำดับใหม่ของลำดับให้เป็นลำดับการเรียงสับเปลี่ยนแบบแบ่งส่วน ซึ่งสามารถทำได้ในเวลาเชิงเส้น โดยการหาค่ามัธยฐานของ ก่อนแล้วจึงย้ายองค์ประกอบไปยังครึ่งแรกหรือครึ่งหลัง ขึ้นอยู่กับว่าองค์ประกอบเหล่านั้นเล็กกว่าหรือมากกว่าค่ามัธยฐาน ${\displaystyle \beta =[b_{1},\dots ,b_{2k}]}$${\displaystyle k}$${\displaystyle [b_{1},\dots ,b_{k}]}$${\displaystyle k}$${\displaystyle [b_{k+1},\dots ,b_{2k}]}$${\displaystyle \beta }$${\displaystyle b}$

ลำดับดังกล่าวสามารถได้มาจากการแบ่งกลุ่มขององค์ประกอบที่ตำแหน่งจากนั้นแบ่งกลุ่มขององค์ประกอบที่ตำแหน่งและจากนั้นแบ่งกลุ่มขององค์ประกอบที่ตำแหน่ง อีกครั้ง สำหรับแต่ละจำนวนเพื่อให้ได้ลำดับที่กำหนดไว้ ${\displaystyle \alpha '}$${\displaystyle [2k(i-1)+1,\dots ,2ki]}$${\displaystyle [2k(i-1)+k+1,\dots ,2ki+k]}$${\displaystyle [2k(i-1)+1,\dots ,2ki]}$${\displaystyle i}$

เมื่อใช้โปรเซสเซอร์ที่ไม่มีการเข้าถึงหน่วยความจำแบบอ่านหรือเขียนร่วมกัน อัลกอริทึมเดียวกันสามารถนำไปใช้กับเวลาได้ เนื่องจากแต่ละส่วนของลำดับสามารถเกิดขึ้นได้พร้อมกัน ${\displaystyle {\frac {n}{2k}}}$${\displaystyle O(k)}$

การรวมลำดับสองลำดับเข้า ด้วย กันสามารถทำได้ในเวลาเชิงเส้นและพื้นที่คงที่ ${\displaystyle k}$${\displaystyle \alpha ^{1}=[a_{1}^{1},\dots ,a_{n}^{1}]}$${\displaystyle \alpha =[a_{1}^{2},\dots ,a_{m}^{2}]}$

ขั้นแรก ใช้ขั้นตอนวิธีที่กล่าวมาข้างต้น แปลงลำดับทั้งสองให้เป็นลำดับที่เรียงลำดับตาม - แล้ว ${\displaystyle k/2}$

เราจะสร้างลำดับเอาต์พุตแบบวนซ้ำโดยการลบเนื้อหาออกจากทั้งสองส่วนแล้วเพิ่มเข้าไปใหม่ ${\displaystyle \omega }$${\displaystyle \alpha ^{i}}$${\displaystyle \omega }$

ถ้าทั้งสองว่างเปล่า ก็เพียงพอที่จะส่งคืนค่าเดิม มิฉะนั้น สมมติว่าว่างเปล่าและไม่ใช่ค่าว่างก็เพียงพอที่จะลบเนื้อหาของและเพิ่มเข้าไปในกรณีที่ว่างเปล่าและไม่ใช่ค่าว่างก็คล้ายกันโดยสมมาตร ${\displaystyle \alpha ^{i}}$${\displaystyle \omega }$${\displaystyle \alpha ^{1}}$${\displaystyle \alpha ^{2}}$${\displaystyle \alpha ^{2}}$${\displaystyle \omega }$${\displaystyle \alpha ^{2}}$${\displaystyle \alpha ^{1}}$

ลองพิจารณากรณีที่ทั้งสองรายการไม่ว่างเปล่า ให้เราเรียกและว่า เป็นค่าที่มากที่สุดขององค์ประกอบแรกๆ ของแต่ละรายการ สมมติว่ากรณีอื่นๆ ก็คล้ายกันโดยสมมาตร ลบ ออก จากและ ลบ ออกจากแล้วเพิ่มเข้าไปใน ${\displaystyle \alpha ^{i}}$${\displaystyle A^{1}=\max(a_{i}^{1}\mid 1\leq i\leq k/2)}$${\displaystyle A^{2}=\max(a_{i}^{2}\mid 1\leq i\leq k/2)}$${\displaystyle k/2}$${\displaystyle A^{1}<A^{2}}$${\displaystyle a_{1}^{1},\dots ,a_{k/2}^{1}}$${\displaystyle \alpha ^{1}}$${\displaystyle \{a_{j}^{2}\mid 1\leq j\leq k/2,a_{j}^{2}\leq A^{1}\}}$${\displaystyle \alpha ^{2}}$${\displaystyle \omega }$

ลำดับ ที่เรียงลำดับแล้วสามารถเรียงลำดับได้โดยใช้อัลกอริธึมการแบ่งครึ่งที่กล่าวไว้ข้างต้นหลายครั้ง ซึ่งใช้เวลาบนเครื่องประมวลผลแบบลำดับ หรือใช้เวลาบน เครื่องประมวลผลแบบหลาย โปรเซสเซอร์ ${\displaystyle k}$${\displaystyle \log _{2}(k)}$${\displaystyle O(n\log k)}$${\displaystyle O(k\log k)}$${\displaystyle O(n)}$

เนื่องจากแต่ละลำดับนั้น เรียงลำดับ ตามค่า n อยู่แล้ว จึงเพียงพอที่จะใช้อัลกอริธึมการแบ่งครึ่งจำนวน n ครั้ง ดังนั้นการเรียงลำดับตามค่า n จึงสามารถทำได้ในเวลา n อัลกอริธึมนี้เป็น อัลกอริธึมที่ดีที่สุดในแง่ ของ Parกล่าวคือ ไม่มีอัลกอริธึมเชิงลำดับใดที่มีความซับซ้อนในกรณีที่เลวร้ายที่สุดดีกว่านี้ ${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$${\displaystyle n}$${\displaystyle \log _{2}\left({\frac {n}{k}}\right)}$${\displaystyle k}$${\displaystyle O(n\log(n/k))}$

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