cs302project2/quick.cpp at main · washwor1/cs302project2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// quick.cpp
//jay ashworth and andy zeng


#include "volsort.h"

#include <iostream>
#include <vector>
using namespace std;
// Prototypes

Node *qsort(Node *head, bool numeric);
void  partition(Node *head, Node *pivot, Node *&left, Node *&right, bool numeric);
Node *concatenate(Node *left, Node *right);

// Implementations

//wrapper function for qsort. same function as wrapper for merge.
void quick_sort(List &l, bool numeric) {
    l.head=qsort(l.head,numeric);
}


//similar driver function to merge with the exception of adding the pivot before merging the whole thing
Node *qsort(Node *head, bool numeric) {
    Node *left=nullptr,*right=nullptr;
    if ((head == nullptr) || head->next == nullptr) {
        return head;
    }
    partition(head,head,left,right, numeric);
    left = qsort(left,numeric);
    right = qsort(right,numeric);
    head->next=nullptr;
    left = concatenate(left,head);
    return concatenate(left,right);
}


//partition function. After checking for numeric, the function loops to iterate through the node string starting at head and calculates whether curr node is greater or lesser.
//If it is lesser, the node is put into left and if it is greater, it is put into right. I also implemented section after the loop that makes the final pointer in each node string
//equal to nullptr
void partition(Node *head, Node *pivot, Node *&left, Node *&right, bool numeric) {
    Node *curr = pivot->next;
    Node *currRight = nullptr,*currLeft =nullptr;
    if (numeric) {
        while(curr!=nullptr){
            if(curr->number>=pivot->number) {
                if (right == nullptr) {
                    right = curr;
                    currRight = right;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
                else{
                    currRight->next = curr;
                    currRight = currRight->next;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
            }
            else {
                if (left == nullptr) {
                    left = curr;
                    currLeft = left;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
                else{
                    currLeft->next = curr;
                    currLeft = currLeft->next;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
            }
        }
        if(left != nullptr) {
            currLeft->next = nullptr;
        }
        if(right != nullptr){
            currRight->next = nullptr;
        }
    }
    else {
        while(curr!=nullptr){
            if(curr->string.compare(pivot->string) >= 0) {
                if (right == nullptr) {
                    right = curr;
                    currRight = right;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
                else{
                    currRight->next = curr;
                    currRight = currRight->next;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
            }
            else {
                if (left == nullptr) {
                    left = curr;
                    currLeft = left;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
                else{
                    currLeft->next = curr;
                    currLeft = currLeft->next;
                    if (curr->next==nullptr){
                        break;
                    }
                    curr = curr->next;
                }
            }
        }
        if(left != nullptr) {
            currLeft->next = nullptr;
        }
        if(right != nullptr){
            currRight->next = nullptr;
        }
    }
}

//iterates through left until it reaches a null. Then adds right as the next node in left and returns left as the head of the newly combined Node string.
Node *concatenate(Node *left, Node *right) {
    Node *currLeft =nullptr;
    currLeft=left;
    if (left == nullptr) {
        return right;
    }
    while(currLeft->next!=nullptr) {
        currLeft = currLeft->next;
    }
    currLeft->next=right;
    return left;
}