One of the basic problems of comput

One of the basic problems of computer science is sorting a list of items. It refers to the arranging of numerical or alphabetical or character data in statistical order (either in increasing order or decreasing order) or in lexicographical order (alphabetical value like addressee key) [1-3]. There are a number of solutions to this problem, known as sorting algorithms. There are several elementary and advanced sorting algorithms. Some sorting algorithms are simple and spontaneous, such as the bubble sort. Others, such as the quick sort are enormously complex, but produce super-fast results. Some sorting algorithm work on less number of elements, some are suitable for floating point numbers, some are good for specific range, some sorting algorithms are used for huge number of data, and some are used if the list has repeated values. Other factors to be considered in choosing a sorting algorithm include the programming effort, the number of words of main memory available, the size of disk or tape units and the extent to which the list is already ordered [4]. That means all sorting Algorithms are problem specific, meaning they work well on some specific problem and do not work well for all the problems. However, there is a direct correlation between the complexity of an algorithm and its relative effectiveness [5]. Many different sorting algorithms have been developed and improved to make sorting fast.
The classical bubble sort, selection sort, and insertion sort are very simple algorithms, often included in the text books to introduce algorithms and sorting, having runtime complexity of Ο(n2) making them impractical to use. The selection sort has a slight better running time than the simplest bubble sort algorithm and worse than the insertion sort. Ityields around 60% performance improvement over the bubble sort, but the insertion sort is over twice as fast as the bubble sort and is just as easy to implement as the selection sort [6]. Though other better techniques such as divide and conquer [7] exist, still there are scopes for fine-tuning these algorithms. Philosophy of these simple algorithms most closely matches human intuition [8]. They can be classified as an in-place [9] and a comparison sort [10].
In the classical selection sort algorithm to sort a list with n data elements n-1 passes are carried out. Each pass finds out the largest or the smallest data item. To do this the entire list is checked form the beginning until the portion of the list, which was sorted in the earlier passes. But, instead of looking from the start of the list in each pass, some information regarding the locations of the local maximum or minimum gathered and stored in the earlier iterations can be used to omit some useless search operations and the overall runtime can be reduced. The enhanced selection sort algorithm is based on this idea. The bubble sort also places the largest element in the proper location in each pass. As the bubble sort and selection sort are closely analogous, the enhancement of the bubble sort is done with the same method. In the classical insertion sort a sorted portion is maintained and in each pass of the algorithm a data item from the unsorted portion is inserted into the sorted portion from a certain side such that with the additional item it remains sorted. Considering just one side to insert leads many shift operations, which can be reduced if both sides of the sorted list is considered to insert a data item. The enhanced insertion sort incorporates this strategy.
This paper is organized in the following order. In Section 2 some previous works relating to improvement of these sorting algorithms are discussed briefly. Section 3 introduces the classical versions of each algorithm followed by detailed discussion and analysis of the proposed enhanced algorithms. Section 5 summarizes and concludes this paper after discussion of the results in Section 4 that shows superiority of the new algorithms.

ผลลัพธ์ (ไทย) 1:

ปัญหาพื้นฐานของวิทยาการคอมพิวเตอร์อย่างใดอย่างหนึ่งจะเรียงลำดับรายการ การจัดเรียงข้อมูลตัวเลข หรือตัวอักษร หรืออักขระตามลำดับสถิติ (อย่างใดอย่างหนึ่งในการเพิ่มใบสั่ง หรือใบสั่งลดลง) หรือ lexicographical ตามลำดับ (ค่าตัวอักษรเช่นแป้นปลาย) [1-3] มีปัญหา เป็นอัลกอริทึมการเรียงลำดับจำนวน มีหลายระดับประถมศึกษา และขั้นสูงเรียงอัลกอริทึม อัลกอริทึมบางเรียงจะง่าย และ ขาด เช่นการเรียงลำดับแบบฟอง อื่น ๆ เช่นเรียงลำดับด่วนซับซ้อนมหาศาล แต่ผลลัพธ์เตอร์รุ่น งานขั้นตอนวิธีการเรียงลำดับจำนวนน้อยองค์ประกอบ บางเหมาะสำหรับจำนวนจุดลอยตัว มีดีเฉพาะช่วง ใช้อัลกอริทึมบางเรียงจำนวนข้อมูลขนาดใหญ่ และบางส่วนใช้ถ้ารายการมีซ้ำค่า ปัจจัยอื่น ๆ เพื่อพิจารณาในการเลือกอัลกอริทึมการเรียงลำดับรวมพยายามเขียนโปรแกรม จำนวนของหน่วยความจำหลัก ขนาดของหน่วยดิสก์หรือเทป และขอบเขตที่รายชื่อแล้วสั่ง [4] ว่า อัลกอริทึมเรียงลำดับทั้งหมดมีปัญหาเฉพาะ หมายความว่า พวกเขาทำงานดีในปัญหาเฉพาะ และไม่ทำงานดีสำหรับทุกปัญหา อย่างไรก็ตาม มีความสัมพันธ์โดยตรงระหว่างความซับซ้อนของขั้นตอนวิธีการและประสิทธิผลของญาติ [5] กระบวนเรียงลำดับแตกต่างกันมากมีการพัฒนา และปรับปรุงเพื่อให้การเรียงลำดับอย่างรวดเร็วเรียงลำดับแบบฟองคลาสสิก เลือกเรียงลำดับ การเรียงลำดับแบบแทรกจะง่ายมากอัลกอริทึม มักจะรวมอยู่ในหนังสือข้อความแนะนำอัลกอริทึม และการเรียงลำดับ การมีความซับซ้อนในการรันไทม์ของ Ο(n2) ทำให้พวกเขาได้ใช้ การเรียงลำดับแบบเลือกมีเวลาทำงานดีขึ้นเล็กน้อยกว่าฟองง่ายอัลกอริทึมการเรียงลำดับ และเรียงลำดับแย่กว่าแทรก Ityields ประมาณ 60% ปรับปรุงประสิทธิภาพเหนือการเรียงลำดับแบบฟอง แต่การเรียงลำดับแบบแทรกเป็นมากกว่าสองครั้งอย่างรวดเร็วเป็นการเรียงลำดับแบบฟอง และการใช้เป็นตัวเลือกการเรียงลำดับ [6] ว่ามีดีกว่าเทคนิคอื่น ๆ เช่นแบ่ง และพิชิต [7] ยังคงมีขอบเขตสำหรับอัลกอริทึมเหล่านี้เพื่อให้เกิดการ ปรัชญาของอัลกอริทึมเหล่านี้อย่างใกล้ชิดมากที่สุดตรงกับสัญชาตญาณมนุษย์ [8] พวกเขาสามารถจัดประเภทเป็นแบบแทน [9] และการเปรียบเทียบเรียงลำดับ [10]ในอัลกอริทึมการเรียงลำดับเลือกคลาสสิกเพื่อเรียงลำดับรายการที่ n ส่งผ่านข้อมูลองค์ประกอบ n-1 จะดำเนินการ ผ่านแต่ละค้นหารายการข้อมูลที่น้อยที่สุดหรือใหญ่ที่สุด ทำการตรวจสอบเป็นต้นจนถึงส่วนของรายการ ซึ่งถูกเรียงลำดับในผ่านก่อนหน้า แต่ แทนที่จะมองจากจุดเริ่มต้นของรายการในแต่ละ ผ่าน ข้อมูลเกี่ยวกับสถานที่เก็บของสูงสุดภายใน หรือสามารถใช้รวบรวม และจัดเก็บในการวนซ้ำก่อนอย่างน้อยให้ละเว้นการดำเนินการบางอย่างค้นหาประโยชน์ และขณะทำงานโดยรวมจะลดลง อัลกอริทึมการเรียงลำดับตัวเลือกขั้นสูงจะขึ้นอยู่กับความคิดนี้ การเรียงลำดับแบบฟองยังวางองค์ประกอบที่ใหญ่ที่สุดในตำแหน่งเหมาะสมในแต่ละด่าน เรียงลำดับแบบฟองและการเรียงลำดับแบบเลือก มีคู่อย่างใกล้ชิด เพิ่มประสิทธิภาพของการเรียงลำดับแบบฟองจะทำ ด้วยวิธีเดียวกัน ในการเรียงลำดับแบบแทรกคลาสสิก ส่วนเรียงลำดับไว้ และในแต่ละรอบของอัลกอริทึมรายการข้อมูลจากส่วน unsorted จะแทรกส่วนเรียงลำดับจากด้านบางที่สินค้าเพิ่มเติมจะยังคงเรียงลำดับ พิจารณาด้านใดด้านหนึ่งเพียงใส่เป้าหมายมากกะการดำเนินงาน ซึ่งสามารถลดลงทั้งสองด้านของรายการเรียงลำดับถือว่าเป็นการแทรกรายการข้อมูล การเรียงลำดับแบบแทรกขั้นสูงประกอบด้วยกลยุทธ์นี้เอกสารนี้ถูกจัดเรียงในลำดับต่อไปนี้ ใน 2 ส่วน บางงานก่อนหน้านี้ที่เกี่ยวข้องกับการปรับปรุงอัลกอริทึมการเรียงลำดับเหล่านี้จะกล่าวถึงสั้น ๆ หมวดที่ 3 แนะนำรุ่นคลาสสิกของแต่ละอัลกอริทึมตามรายละเอียดอธิบายและวิเคราะห์ของอัลกอริทึมนำเสนอขั้นสูง ส่วนที่ 5 สรุป และสรุปเอกสารนี้หลังจากอภิปรายผลใน 4 ส่วนที่แสดงปมของอัลกอริทึมใหม่

ผลลัพธ์ (ไทย) 2:

หนึ่งในปัญหาพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์การเรียงลำดับรายชื่อของรายการ มันหมายถึงการจัดของตัวเลขหรือตัวอักษรหรือข้อมูลตัวอักษรในการสั่งซื้อทางสถิติ (ทั้งในการเพิ่มการสั่งซื้อหรือสั่งซื้อลดลง) หรือเพื่อ lexicographical (มูลค่าที่เรียงตามตัวอักษรเช่นที่สำคัญผู้รับ) [1-3] มีจำนวนของการแก้ปัญหานี้เป็นที่รู้จักการเรียงลำดับขั้นตอนวิธี มีหลายระดับประถมศึกษาและขั้นสูงการเรียงลำดับขั้นตอนวิธี บางขั้นตอนวิธีการเรียงลำดับจะง่ายและเกิดขึ้นเองเช่นการจัดเรียงฟอง อื่น ๆ เช่นการจัดเรียงอย่างรวดเร็วมีความซับซ้อนอย่างมาก แต่ผลลัพธ์ที่ได้อย่างรวดเร็ว บางงานขั้นตอนวิธีการเรียงลำดับในจำนวนน้อยขององค์ประกอบบางอย่างที่เหมาะสำหรับการลอยหมายเลขจุดบางส่วนเป็นสิ่งที่ดีสำหรับช่วงที่เฉพาะเจาะจงบางขั้นตอนวิธีการเรียงลำดับจะใช้สำหรับจำนวนมากข้อมูลและบางส่วนจะใช้ในกรณีที่รายการได้ซ้ำแล้วซ้ำอีกค่า ปัจจัยอื่น ๆ ที่ได้รับการพิจารณาในการเลือกขั้นตอนวิธีการเรียงลำดับรวมถึงความพยายามในการเขียนโปรแกรม, จำนวนของคำหลักของหน่วยความจำที่มีขนาดของดิสก์หรือหน่วยเทปและขอบเขตที่รายการได้รับคำสั่งแล้ว [4] นั่นหมายถึงขั้นตอนวิธีการเรียงลำดับทั้งหมดเป็นปัญหาที่เฉพาะเจาะจงหมายถึงพวกเขาทำงานได้ดีในการแก้ปัญหาบางอย่างและไม่ได้ทำงานได้ดีสำหรับทุกปัญหา แต่มีความสัมพันธ์โดยตรงระหว่างความซับซ้อนของขั้นตอนวิธีการและประสิทธิผลของญาติ [5] หลายขั้นตอนวิธีการเรียงลำดับที่แตกต่างกันได้รับการพัฒนาและปรับปรุงเพื่อให้การเรียงลำดับอย่างรวดเร็ว.
การจัดเรียงฟองคลาสสิก, การจัดเรียงตัวเลือกและแทรกการจัดเรียงเป็นขั้นตอนวิธีการที่ง่ายมากมักจะรวมอยู่ในหนังสือที่จะแนะนำขั้นตอนวิธีการและการเรียงลำดับมีความซับซ้อนรันไทม์ของΟ (N2) ทำให้พวกเขาทำไม่ได้ที่จะใช้ การจัดเรียงตัวเลือกมีเล็กน้อยเวลาทำงานดีกว่าขั้นตอนวิธีการจัดเรียงฟองที่ง่ายและเลวร้ายยิ่งกว่าการจัดเรียงแทรก Ityields ประมาณ 60% ปรับปรุงประสิทธิภาพการทำงานมากกว่าการจัดเรียงฟอง แต่การจัดเรียงแทรกที่มีมากกว่าสองครั้งที่รวดเร็วเป็นจัดเรียงฟองและเป็นเพียงเป็นเรื่องง่ายที่จะใช้เป็นตัวเลือกการจัดเรียง [6] แม้ว่าเทคนิคที่ดีกว่าอื่น ๆ เช่นการแบ่งและพิชิต [7] มีอยู่ก็ยังมีขอบเขตสำหรับการปรับเปลี่ยนขั้นตอนวิธีการเหล่านี้ ปรัชญาของขั้นตอนวิธีง่ายๆเหล่านี้อย่างใกล้ชิดที่สุดตรงกับสัญชาตญาณของมนุษย์ [8] พวกเขาสามารถจัดเป็นในสถานที่ [9] และการเปรียบเทียบการเรียงลำดับ [10].
ในขั้นตอนวิธีการจัดเรียงตัวเลือกคลาสสิกที่จะเรียงลำดับรายการที่มีองค์ประกอบข้อมูล n n-1 ที่ผ่านมามีการดำเนินการ ผ่านแต่ละพบที่ใหญ่ที่สุดหรือรายการข้อมูลที่มีขนาดเล็กที่สุด การทำเช่นนี้รายชื่อทั้งหมดมีการตรวจสอบรูปแบบจุดเริ่มต้นจนถึงส่วนของรายการซึ่งได้รับการเรียงผ่านก่อนหน้านี้ แต่แทนที่จะมองจากจุดเริ่มต้นของรายการในแต่ละผ่านข้อมูลบางอย่างเกี่ยวกับสถานที่สูงสุดในประเทศหรือขั้นต่ำที่รวบรวมและเก็บไว้ในการทำซ้ำก่อนหน้านี้สามารถใช้ในการละเว้นการดำเนินการค้นหาบางไร้ประโยชน์และรันไทม์โดยรวมจะลดลง ขั้นตอนวิธีการจัดเรียงตัวเลือกที่เพิ่มขึ้นจะขึ้นอยู่กับความคิดนี้ การจัดเรียงฟองยังสถานที่องค์ประกอบที่ใหญ่ที่สุดในตำแหน่งที่เหมาะสมในแต่ละผ่าน ในขณะที่การจัดเรียงฟองและการจัดเรียงตัวเลือกที่มีความคล้ายคลึงกันอย่างใกล้ชิด, การเพิ่มประสิทธิภาพของการจัดเรียงฟองจะทำด้วยวิธีการเดียวกัน ในการแทรกคลาสสิกการเรียงลำดับเรียงลำดับส่วนจะถูกเก็บไว้และในแต่ละขั้นตอนวิธีการผ่านรายการข้อมูลจากส่วนที่ไม่ได้เรียงลำดับถูกแทรกลงในส่วนที่เรียงลำดับจากข้างเคียงบางอย่างเช่นที่กับรายการเพิ่มเติมก็ยังคงถูกจัดเรียง พิจารณาเพียงด้านเดียวที่จะนำไปสู่การดำเนินการแทรกการเปลี่ยนแปลงจำนวนมากซึ่งสามารถลดลงได้ถ้าทั้งสองด้านของรายการที่เรียงลำดับมีการพิจารณาที่จะแทรกรายการข้อมูล จัดเรียงแทรกที่เพิ่มขึ้นรวมกลยุทธ์นี้.
กระดาษนี้จะจัดในลำดับต่อไป ในส่วนที่ 2 บางส่วนก่อนหน้างานที่เกี่ยวข้องกับการปรับปรุงขั้นตอนวิธีการเรียงลำดับเหล่านี้จะกล่าวสั้น ๆ ส่วนที่ 3 แนะนำรุ่นคลาสสิกของอัลกอริทึมแต่ละตามด้วยการอภิปรายรายละเอียดและการวิเคราะห์การปรับปรุงขั้นตอนวิธีการที่นำเสนอ หมวดที่ 5 สรุปและสรุปบทความนี้หลังจากการอภิปรายของผลในมาตรา 4 ที่แสดงให้เห็นถึงความเหนือกว่าของอัลกอริทึมใหม่

ผลลัพธ์ (ไทย) 3:

หนึ่งในปัญหาพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์เป็นรายชื่อรายการเรียงลำดับ มันหมายถึงการจัดเรียงของตัวเลขหรือตัวอักษรหรือตัวอักษรเพื่อให้ข้อมูลทางสถิติ เพื่อเพิ่มหรือลดคำสั่ง ) หรือในการจัดลำดับแบบพจนานุกรม ( ตัวอักษรมูลค่าชอบคีย์ผู้รับ ) [ 1-3 ] มีจำนวนของวิธีแก้ไขปัญหานี้ เรียกว่าขั้นตอนวิธีการเรียงลำดับ .มีหลายระดับและขั้นสูงขั้นตอนวิธีการเรียงลำดับ . ขั้นตอนวิธีการเรียงลำดับบางอย่างง่ายและธรรมชาติ เช่น ฟองเรียง . อื่นๆ เช่น การจัดเรียงอย่างรวดเร็วมีความซับซ้อนเป็นอย่างมาก แต่ให้ผลลัพธ์ที่เร็วสุด . บางขั้นตอนวิธีงานจำนวนน้อยขององค์ประกอบของการจัดเรียงบาง เหมาะสำหรับจุดลอยตัวเลขบางอย่างที่ดีสำหรับช่วงที่เฉพาะเจาะจงขั้นตอนวิธีการเรียงลำดับบางอย่างจะใช้สำหรับตัวเลขขนาดใหญ่ของข้อมูล และบางคนก็ใช้ ถ้ารายการมีซ้ำค่า ปัจจัยอื่น ๆที่จะได้รับการพิจารณาในการเลือกการเรียงลำดับขั้นตอนวิธีรวมถึงโปรแกรมพยายาม จำนวนของคำพูดของหน่วยความจำหลักมีขนาดของดิสก์หรือเทปหน่วยและขอบเขตที่รายการสั่งซื้อแล้ว [ 4 ] ที่หมายทั้งหมดขั้นตอนวิธีการเรียงลำดับโดยเฉพาะปัญหาความหมาย พวกเขาทำงานได้ดีในบางปัญหาที่เฉพาะเจาะจงและไม่ทำงานได้ดีสำหรับปัญหาทั้งหมด อย่างไรก็ตาม มีความสัมพันธ์โดยตรงระหว่างความซับซ้อนของขั้นตอนวิธีและประสิทธิภาพสัมพัทธ์ [ 5 ] หลายขั้นตอนวิธีการเรียงลำดับได้รับการพัฒนาและปรับปรุงเพื่อให้เรียงลำดับอย่างรวดเร็ว
เรียงฟองคลาสสิก , การจัดเรียงและการจัดเรียงใส่เป็นกลไกที่ง่ายมากมักจะรวมอยู่ในตำราแนะนำขั้นตอนวิธีการเรียงลำดับและมีความซับซ้อนของΟ Runtime ( N2 ) ทำให้พวกเขายากมากที่จะใช้ การจัดเรียงมีเล็กน้อยดีกว่าวิ่งเวลากว่าง่ายฟองเรียงลำดับขั้นตอนวิธีและแย่กว่าการจัดเรียง ityields ประมาณ 60 % การปรับปรุงประสิทธิภาพกว่าฟองเรียงลําดับแต่การจัดเรียงมากกว่าสองครั้งที่รวดเร็วเป็นฟองเรียงและเป็นเพียงเป็นเรื่องง่ายที่จะใช้ เช่น การจัดเรียง [ 6 ] แต่ที่ดีๆ เทคนิค เช่น แบ่งและพิชิต [ 7 ] อยู่ ยังคงมีขอบเขตสำหรับการปรับขั้นตอนวิธีเหล่านี้ ปรัชญาของขั้นตอนวิธีง่ายๆเหล่านี้ส่วนใหญ่ตรงกับมนุษย์สัญชาตญาณ [ 8 ]พวกเขาสามารถจัดเป็นหนึ่งในสถานที่ [ 9 ] และการจัดเรียง [ 10 ] .
ในคลาสสิกการจัดเรียงแบบขั้นตอนวิธีการจัดเรียงรายการด้วยข้อมูลองค์ประกอบ N - 1 ผ่านจะดําเนินการ ผ่านแต่ละพบมากที่สุด หรือน้อยที่สุด ข้อมูลสินค้า การทำรายการทั้งหมดจะถูกตรวจสอบจากจุดเริ่มต้นจนถึงส่วนของรายการ ซึ่งในการเรียงลำดับผ่านก่อน แต่แทนที่จะมองจากจุดเริ่มต้นของรายการในการผ่านแต่ละ บางข้อมูลเกี่ยวกับตำแหน่งสูงสุดหรือต่ำสุดท้องถิ่นรวบรวมและเก็บไว้ในการทำซ้ำก่อนหน้านี้สามารถใช้ที่จะละเว้นบางการค้นหาไร้ประโยชน์และ runtime โดยรวมจะลดลง ปรับปรุงขั้นตอนวิธีการจัดเรียงตามความคิดนี้ฟองเรียงสถานที่องค์ประกอบที่ใหญ่ที่สุดในสถานที่ที่เหมาะสมในการส่งแต่ละ เป็นฟองเรียง และการจัดเรียงที่คล้ายกันอย่างใกล้ชิด , การเพิ่มประสิทธิภาพของฟองเรียงเสร็จแล้ว ด้วยวิธีเดียวกันในคลาสสิกแทรกเรียงเรียง ส่วนจะรักษาและในแต่ละรอบของอัลกอริทึมข้อมูลจากส่วนเรียงถูกแทรกลงในบางด้าน เช่น ส่วนที่แยกจากกับรายการเพิ่มเติมก็ยังคงเรียงลําดับ พิจารณาเพียงหนึ่งข้าง เพื่อนำไปสู่การใส่กะหลายซึ่งสามารถลด ถ้าทั้งสองฝ่ายแยกรายการถือว่าแทรกรายการข้อมูล เพิ่มการเรียงลำดับแบบแทรก ซึ่งกลยุทธ์นี้ .
กระดาษนี้ถูกจัดอยู่ในลำดับต่อไปนี้ ในส่วนของงานที่เกี่ยวข้องกับการปรับปรุงก่อนหน้านี้ 2 บางเหล่านี้ขั้นตอนวิธีการเรียงลำดับมีการกล่าวถึงสั้น ๆส่วนที่ 3 แนะนำรุ่นคลาสสิกของแต่ละขั้นตอน ตามด้วยการอภิปรายรายละเอียดและการวิเคราะห์อัลกอริทึมใหม่เพิ่ม มาตรา 5 ได้รวบรวมและสรุปบทความนี้หลังจากการอภิปรายผลในมาตรา 4 ที่แสดงความเหนือกว่าของอัลกอริทึมใหม่