C Programming: Sorting

Selection Sort

• เป็น sort ที่เรียบง่าย ไม่ซับซ้อน และมีประสิทธิภาพในการทำงาน
• ใช้หลักการทำงาน หาค่าน้อยที่สุด สำหรับแต่ละตำแหน่งของข้อมูล
• Time complexity (Big-O) = n^2

Instruction

1. เริ่มต้นจากนำข้อมูลทั้งหมดที่ยังไม่ได้เรียงมาตั้งต้น
2. เริ่มวนข้อมูลตั้งแต่ตำแหน่งแรก
3. ที่ตำแหน่งแรกให้หาตำแหน่งของข้อมูลที่มีค่าน้อยที่สุดใน array นั้น
4. จากนั้นให้สลับข้อมูลตำแหน่งแรกกับตำแหน่งที่ข้อมูลมีค่าน้อยที่สุด
5. เริ่มวนข้อมูลตำแหน่งที่ 2 โดยใช้กรอบตำแหน่งข้อมูลตั้งแต่ ตำแหน่งที่ 2 - สุดท้าย
6. ทำเหมือนข้อ 3) เมื่อเจอข้อมูลที่น้อยที่สุดให้สลับข้อมูล ตำแหน่งข้อมูลที่ 2 กับ ข้อมูลที่น้อยที่สุด (เหมือนข้อ 4)
7. วนทำงานไปเรื่อยๆ จนตำแหน่งสุดท้าย

Example Code

#include <stdio.h>

int main() {
  int list[] = { 5, 1, 6, 12, 4, 3, 8, 33, 16, 21 };
  int size = sizeof(list) / sizeof(list[0]);
  int smallest, tempData = 0;

  for (int current = 0; current < size; current++) {
      smallest = current;
      for (int walk = current + 1; walk <= size; walk++) {
        if (list[walk] < list[smallest]) {
          smallest = walk;
        }
      }

      tempData = list[current];
      list[current] = list[smallest];
      list[smallest] = tempData;
  }
}

Bubble Sort

• ใช้หลักการสลับค่าที่น้อยกว่า (หรือมากกว่า) กับลำดับก่อนหน้าไปเรื่อยๆ
• ค่าที่น้อยกว่า (หรือมากกว่า) จะถูกสลับขึ้นไปข้างบนเรื่อยๆ ในแต่ละรอบของการวน จึงถูกเรียกว่า Bubble = ค่าลอยขึ้นเหมือนฟอง
• ไม่เหมาะกับข้อมูลขนาดใหญ่ เพราะมีการวนค่าซ้ำหลายรอบ
• Time Complexity (Big-O) = n^2

Instruction

1. เริ่มต้นจากนำข้อมูลทั้งหมดที่ยังไม่ได้เรียงมาตั้งต้น
2. เริ่มวนข้อมูลตำแหน่งสุดท้ายถึงตำแหน่งแรก
3. ระหว่างที่วนแต่ละรอบย่อย ให้เปรียบเทียบว่าค่าใดน้อยกว่า (ข้อมูลนี้กับข้อมูลก่อนหน้า) ถ้าข้อมูลน้อย กว่าให้สลับที่ ทำไปเรื่อยๆ จนสลับถึงตำแหน่งแรก
4. เริ่มวนรอบต่อไป โดยเริ่มจากตำแหน่งสุดท้าย ถึงตำแหน่งที่ 2
5. ทำเหมือนกับข้อ 3)
6. ทำแบบนี้จนถึงรอบสุดท้าย (ตำแหน่งสุดท้าย - ตำแหน่งก่อนสุดท้าย)

Example Code

#include <stdio.h>

int main() {
  int list[] = { 5, 6, 12, 4, 3, 8, 33, 16, 21, 1 };
  int size = sizeof(list) / sizeof(list[0]);
  // Local Declarations
  int temp = 0;

  // Statements
  // Outer loop
  for(int current = 0; current < size; current++)
  {
      // Inner loop: Bubble up one element each pass
      for (int walker = size - 1; walker > current; walker--) {
          printf("%d", walker);
          if (list[walker] < list[walker - 1]) {
              temp = list[walker];
              list[walker] = list[walker - 1];
              list[walker - 1] = temp;
          }
      } // for walker
  }
}

Insertion Sort

• หลักการคล้ายกับการเรียงไพ่ในมือ โดยจะมีการสลับตัวที่น้อย (หรือมากกว่า) และแทรกกลับไปที่ตำแหน่งที่ข้อมูลควรจะอยู่
• ประสิทธิภาพจะต่ำเมื่อเจอข้อมูลก่อนจัดเรียงที่มีการเรียงตัวตรงกันข้ามกับผลลัพธ์ที่ต้องการ
• Time Complexity (Big-O) = n^2

Instruction

1. เริ่มต้นจากนำข้อมูลทั้งหมดที่ยังไม่ได้เรียงมาตั้งต้น
2. เริ่มวนข้อมูลเทียบที่ตัวแรกกับตัวถัดไป ถ้าน้อยกว่าให้สลับที่
3. หลังจากรอบที่ 2
   1. การเทียบข้อมูลตำแหน่งปัจจุบันกับข้อมูลตำแหน่งถัดไป ถ้าข้อมูลตำแหน่งถัดไปน้อยกว่า ก็ให้เทียบย้อนกลับไปที่ข้อมูลตำแหน่งก่อนหน้านั้นทุกตัวด้วย
   2. ถ้าเทียบแล้วข้อมูลไม่น้อยกว่าแล้ว (หรือไม่มากกว่า) ให้หยุดและแทรกข้อมูลที่ตำแหน่งนั้น
   3. ถ้าเทียบแล้วไม่เจอให้วนย้อนกลับไปถึงตำแหน่งแรก (ข้อมูลอาจจะน้อยที่สุดหรือมากที่สุด)
4. ทำแบบนี้ไปเรื่อยๆ จนถึงตำแหน่งสุดท้าย

Example Code

#include <stdio.h>
#include <stdbool.h>

int main() {
  int list[] = { 7, 5, 4, 3, 8, 33, 16, 21, 1 };
  int size = sizeof(list) / sizeof(list[0]);

  // Local Declarations
  int walk;
  int temp;
  bool located;

  // Statements
  // Outer loop
  for (int current = 1; current <= size - 1; current++)
  {
    // Inner loop: Select and move one element
    located = false;
    temp = list[current];
    for (walk = current - 1; walk >= 0 && !located;)
    {
        if (temp < list[walk]) {
            list[walk + 1] = list[walk];
            walk--;
        } else {
            located = true;
        } // else
    } // for
    list[walk + 1] = temp;
  } // for
  printf("%3d", list[0]);
}

Reference

W3Schools.com

W3Schools offers free online tutorials, references and exercises in all the major languages of the web. Covering popular subjects like HTML, CSS, JavaScript, Python, SQL, Java, and many, many more.

C Program For Bubble Sort - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

GeeksforGeeksGeeksforGeeks

Insertion Sort คือ? | Matter Devs

Insertion Sort คือ? การจัดเรียงแบบแทรก มีหลักการคล้ายกับการเรียงไพ่ในมือของคุณ อาร์เรย์จะแบ่งออกเป็นสองส่วน ส่วนที่จัดเรียงแล้วกับส่วนที่ยังไม่ถูกจัดเรียง

Matter DevsHusna