مرتب کردن لیست پیوندی بوسیله مرتب سازی درجی

Question

سلام

من هر قدر فکر کردم نفهمیدم چطوری میشه لیست پیوندی رو  با روش مرتب سازی درجی از کوچیک به بزگ مرتب کرد !!

ممنون میشم کمک کنید ؟؟

Answer 1

روش مرتب‌سازی درج یک الگوریتم مرتب‌سازی ساده است که با قرار دادن مکرر هر عنصر از قسمت مرتب‌نشده فهرست در موقعیت صحیح خود در قسمت مرتب‌شده فهرست کار می‌کند. در اینجا مثالی از نحوه پیاده‌سازی روش مرتب‌سازی درج برای لیست پیوندی منفرد در C++ آورده شده است:

void insertSort(Node* head) {
    Node* sorted = NULL;

    Node* current = head;
    while (current != NULL) {
        // Save the next node
        Node* next = current->next;

        // Insert the current node into the sorted list
        sorted = sortedInsert(sorted, current);

        // Move to the next node
        current = next;
    }

    // Update the head of the list to the new sorted list
    head = sorted;
}

تابع فوق یک اشاره گر را به سر لیست پیوند داده شده به عنوان ورودی می گیرد و با قرار دادن مکرر هر گره از قسمت مرتب نشده لیست در موقعیت صحیح خود در قسمت مرتب شده لیست، لیست را مرتب می کند.

 

نمونه ای از تابع sortedInsert در اینجا آمده است:

Node* sortedInsert(Node* head, Node* newNode) {
    // If the list is empty or the new node is smaller than the head
    if (head == NULL || head->data >= newNode->data) {
        newNode->next = head;
        return newNode;
    }

    // Find the correct position for the new node
    Node* current = head;
    while (current->next != NULL && current->next->data < newNode->data) {
        current = current->next;
    }

    // Insert the new node
    newNode->next = current->next;
    current->next = newNode;

    return head;
}

 

تابع فوق یک اشاره گر به سر لیست مرتب شده و یک اشاره گر به گره ای که باید به عنوان ورودی درج شود می برد. سپس با عبور از لیست مرتب شده، موقعیت صحیح گره جدید را پیدا می کند و با به روز رسانی نشانگرها، گره جدید را در موقعیت صحیح قرار می دهد.

پیچیدگی زمانی الگوریتم مرتب سازی درجی برای یک لیست پیوندی منفرد O(n^2) است.

 

حلقه while خارجی در تابع insertSort روی تمام گره های لیست تکرار می شود و برای هر گره تابع sortedInsert فراخوانی می شود. تابع sortedInsert از طریق قسمت مرتب شده لیست تکرار می شود تا موقعیت صحیح گره جدید را پیدا کند، بنابراین برای هر گره در قسمت مرتب نشده لیست، به طور متوسط n/2 مرحله طول می کشد تا موقعیت صحیح در قسمت مرتب شده را پیدا کند. از لیست

 

از آنجایی که حلقه while بیرونی روی تمام n گره لیست تکرار می شود و برای هر گره تابع sortedInsert به طور متوسط n/2 مرحله طول می کشد، تعداد کل مراحل n * n/2 = n^2/2 = O(n است. ^2)

 

بنابراین، پیچیدگی زمانی این پیاده‌سازی الگوریتم مرتب‌سازی درج برای یک لیست پیوندی منفرد O(n^2) است که برای لیست‌های بزرگ ناکارآمد در نظر گرفته می‌شود. برای لیست‌های بزرگ، سایر الگوریتم‌های مرتب‌سازی مانند مرتب‌سازی سریع یا ادغام با پیچیدگی زمانی O(nlogn) کارآمدتر هستند.