Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
Writing in the front
Hello everyone, MY name is Melo, a sophomore majoring in software engineering. After a year of fumbling, I am now preparing to develop backstage projects in the studio. However, I still want to talk about data structure and algorithm in this article. The course of data structure was not opened until the second year of the university. I hope I can accumulate experience in background project development while learning data structure. The first few articles, we are talking about data structure, it is time to talk about some new tricks, contact some more test thinking and logic of the algorithm, now this stage of the algorithm, we mainly talk about first are sorting algorithm, this section from the most “simple” insertion sort start!
Train of thought
The basic idea of Insertion Sorting is: Read the n to sort elements as an ordered list and an unordered list, at the beginning of the order in the table contains only one element, disorder in the table contains a element of n – 1, each time in the process of sorting table to retrieve the first element from the chaos, combine its sort code in comparing with orderly table element ordering code, in an orderly table to insert it into the appropriate location, Make it the new ordered table.
The summary is: the first n-1 as ordered, and then insert the NTH in the front of the appropriate position, to become a new ordered list
More detailed ideas and procedures are embedded in the comments of the code.
Pay attention to
Sentinel A0 compared to insertValue
- I can leave out the j greater than 0, because the sentinel means, when you get to the sentinel, you’re going to stop
And then finally j plus one is the position
Compare from back to front (note that if the first one is not satisfied, it will not continue to traverse directly)
Force button 912 sort array
I’m going to run out of time by checking each one and then inserting it,n squared, so I’m going to check the last one first, and then I’m going to see if I need to go down
/** * Note: The returned array must be malloced, assume caller calls free(). */
int* sortArray(int* nums, int numsSize, int* returnSize){
// Start with the second number
for(int i=1; i<numsSize; i++){// Save the value to be inserted
int insertValue=nums[i];
int insertIndex=0;
for(int j=i- 1; j>=0; j--){// If the value to be inserted is smaller than the index value, the index value needs to be moved back, leaving this space for the inserted value
if(insertValue<nums[j]){
nums[j+1]=nums[j];
// Record the position to be insertedinsertIndex=j; }}// After breaking out of the loop, insert the number at the specified position
nums[insertIndex]=insertValue;
}
/*returnSize = (int*)malloc(numsSize*sizeof(int)); for(int i=0; i
*returnSize=numsSize;
return nums;
}
Copy the codeTo optimize the
InsertValue <nums[j]
In fact, since the first n minus 1 is already in order, we don’t have to keep iterating if we want to insert more than the last number
Best case: O(n)
The original array is in ascending order and only needs to be compared once in each cycle to proceed to the next cycle, which requires O(n) comparisons in total.
Worst case: O(n^2) (rough)
The original array is in descending order. Any two numbers in the array are compared once, O(n^2) times.
Average case: O(n^2)
Space complexity :O(1)
Only one sentinel position was used
/** * Note: The returned array must be malloced, assume caller calls free(). */
int* sortArray(int* nums, int numsSize, int* returnSize){
int insertValue = 0;
int j;
// Start with the second number
for(int i=1; i<numsSize; i++){// Save the value to be inserted
insertValue=nums[i];
// If the number to be inserted is greater than the last one, there is no need to continue traversing
for(j=i- 1; j>=0&& insertValue<nums[j]; j--){// If the value to be inserted is smaller than the index value, then the index value needs to be moved back
nums[j+1]=nums[j];
}
// After breaking out of the loop, insert the number at the specified position
nums[j+1]=insertValue;
}
/*returnSize = (int*)malloc(numsSize*sizeof(int)); for(int i=0; i
*returnSize=numsSize;
return nums;
}
Copy the code
Sentry set method at 0
u
If you set the sentry at 0, you can omit the judgment that j>0 because you will stop when you reach the sentry
“
#include "allinclude.h" //DO NOT edit this line
void InsertSort(RcdSqList &L)
{ // Add your code here
for(int i=2; i<=L.length; i++){int j=i- 1;
// Record the sentry
L.rcd[0].key=L.rcd[i].key;
// Find the position to insert (in the direction of the sentry, the sentry is in front)
while(L.rcd[j].key>L.rcd[L.length+1].key){
L.rcd[j+1].key=L.rcd[j].key;
j--;
}
// out of the loop,j+1 is the position to insert
L.rcd[j+1].key=L.rcd[L.length+1].key; }}Copy the codeSentry is set to length+1
Because we want to embody the role of the sentinel, we have to embody the role of the sentinel to stop naturally
We used to have I from zero to the end, and then we used a j to go from one element in front of I to the sentry and now we have the sentry behind, so we have to think the other way around. Let I go back to front, so that J can go back to front to back to the sentry
// Just the opposite, I is traversed from back to front
for(int i=L.length- 1; i>=0; i--){int j=i+1;
// If it is smaller than the next one, no need to move it
if(L.rcd[i].key>L.rcd[j].key){
// Record the sentry
L.rcd[L.length+1].key=L.rcd[i].key;
// Find the position to insert (j is to go back, because the sentry is behind)
while(L.rcd[j].key<L.rcd[L.length+1].key){
L.rcd[j- 1].key=L.rcd[j].key;
j++;
}
// Out of the loop,j-1 is the position to insert
L.rcd[j- 1].key=L.rcd[L.length+1].key; }}Copy the codeConclusion the template
-
For (iterating from the second)
- j=i-1; insertVal = a [i]
- while(j>=0 && insertVal < a[j] )
-
a[j+1]=insertVal
Linked list version
The difference between
The difference between arrays and linked lists is that arrays can easily find the previous one, while linked lists can’t, so we need to use an extra pre pointer to record the previous one, and we can optimize it at the same time
Force link 147 inserts sort linked lists
Leetcode-cn.com/problems/in…
The timeout version (honestly go back to the beginning)
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
// Insert element p(directly from the second element)
struct ListNode* p=drumyHead->next->next;
while(p){
struct ListNode* q=drumyHead;
struct ListNode* pos=NULL;
// If you have not traversed the previous position of the element to be inserted
while(q->next! =p){// If the next bit of the current element traversed is larger than the element to be inserted, the element to be inserted should be inserted into the next bit of the current element
if(q->next->val > p->val){
// Record the insertion position
pos=q;
// Jump out! Because instead of going backwards, we're going backwards, like 2, 3, 4, 1
// If 2>1, then you are in the right position
break;
}
/ / move q
q=q->next;
}
// Move q to a position before p
while(q->next! =p){ q=q->next; }// Out of the loop,q already precedes the element p to be inserted
if(pos! =NULL) {// Pay attention to the order
// let q's next= P's next
q->next=p->next;
p->next=pos->next;
pos->next=p;
}
/ / move p
p=p->next;
}
return drumyHead->next;
}
Copy the codeUse the Pre pointer to record the precursor each time you traverse
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
// Insert element p(directly from the second element)
struct ListNode* p=drumyHead->next->next;
// Record the precursor of the element to be inserted, remember to initialize as the first element!!
struct ListNode* pre=drumyHead->next;
while(p){
// Compare with the precursor
if(p->val>pre->val){
pre=p;
p=p->next;
continue;
}
struct ListNode* q=drumyHead;
struct ListNode* pos=NULL;
// If you have not traversed the previous position of the element to be inserted
while(q->next! =p){// If the next bit of the current element traversed is larger than the element to be inserted, the element to be inserted should be inserted into the next bit of the current element
if(q->next->val > p->val){
// Record the insertion position
pos=q;
// Jump out! Because instead of going backwards, we're going backwards, like 2, 3, 4, 1
// If 2>1, then you are in the right position
break;
}
/ / move q
q=q->next;
}
// move q to the position before p (because the front breaks)
while(q->next! =p){ q=q->next; }// Out of the loop,q already precedes the element p to be inserted
if(pos! =NULL) {// Pay attention to the order
// let q's next= P's next
q->next=p->next;
p->next=pos->next;
pos->next=p;
}
// Update the precursor
pre=p;
/ / move p
p=p->next;
}
return drumyHead->next;
}
Copy the codeIt takes about 360ms
Time optimization (judge precursors in while instead of continue)
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
// Insert element p(directly from the second element)
struct ListNode* p=drumyHead->next->next;
// Record the precursor of the element to be inserted, remember to initialize as the first element!!
struct ListNode* pre=drumyHead->next;
struct ListNode* q;
struct ListNode* pos;
while(p){
// // first compare with the precursor (this is much lower efficiency, so it takes 300ms, change the following while judgment only needs 40ms)
// if(p->val>pre->val){
// pre=p;
// p=p->next;
// continue;
// }
q=drumyHead;
pos=NULL;
// Check if it is smaller than the precursor, if it is not, don't loop directly!!
// If you have not traversed the previous position of the element to be inserted
while(q->next! =p&&p->val<pre->val){// If the next bit of the current element traversed is larger than the element to be inserted, the element to be inserted should be inserted into the next bit of the current element
if(q->next->val > p->val){
// Record the insertion position
pos=q;
// Jump out! Because instead of going backwards, we're going backwards, like 2, 3, 4, 1
// If 2>1, then you are in the right position
break;
}
/ / move q
q=q->next;
}
// There is no need, because there is pre to record the last position of p
// // moves q to a position in front of p (because the front breaks) for easy operation
// while(q->next! =p){
// q=q->next;
// }
// Check pos to see if it needs to be inserted
if(pos! =NULL) {// Pay attention to the order
// let q's next= P's next
pre->next=p->next;
p->next=pos->next;
pos->next=p;
}
// Update the precursor
pre=p;
/ / move p
p=p->next;
}
return drumyHead->next;
}
Copy the codeIt takes about 40ms
Put if in the outermost layer, the best time (36ms)
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /
struct ListNode* insertionSortList(struct ListNode* head){
struct ListNode* drumyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
drumyHead->next=head;
// Insert element p(directly from the second element)
struct ListNode* p=drumyHead->next->next;
// Record the precursor of the element to be inserted, remember to initialize as the first element!!
struct ListNode* pre=drumyHead->next;
struct ListNode* q;
struct ListNode* pos;
while(p){
// // first compare with the precursor
// if(p->val>pre->val){
// pre=p;
// p=p->next;
// continue;
// }
// Compare directly here, try not to continue
if(p->val<pre->val){
q=drumyHead;
pos=NULL;
// If you have not traversed the previous position of the element to be inserted
while(q->next! =p){// If the next bit of the current element traversed is larger than the element to be inserted, the element to be inserted should be inserted into the next bit of the current element
if(q->next->val > p->val){
// Record the insertion position
pos=q;
// Jump out! Because instead of going backwards, we're going backwards, like 2, 3, 4, 1
// If 2>1, then you are in the right position
break;
}
/ / move q
q=q->next;
}
// // moves q to a position in front of p (because the front breaks) for easy operation
// while(q->next! =p){
// q=q->next;
// }
// Out of the loop,q already precedes the element p to be inserted
if(pos! =NULL) {// Pay attention to the order
// let q's next= P's nextpre->next=p->next; p->next=pos->next; pos->next=p; }}// Update the precursor
pre=p;
/ / move p
p=p->next;
}
return drumyHead->next;
}
Copy the code
Continue Time consuming test
The test method
Call the stamp method below to print the time before and after insertion sort respectively
#include <ctime>
#include <string>
#include <chrono>
#include <sstream>
#include <iomanip>
#include <iostream>
// use strftime to format time_t into a "date time"
std: :string date_time(std: :time_t posix)
{
char buf[20]; // big enough for 2015-07-08 10:06:51\0
std::tm tp = *std::localtime(&posix);
return {buf, std::strftime(buf, sizeof(buf), "%F %T", &tp)};
}
std: :string stamp(a)
{
using namespace std;
using namespace std::chrono;
// get absolute wall time
auto now = system_clock::now();
// find the number of milliseconds
auto ms = duration_cast<milliseconds>(now.time_since_epoch()) % 1000;
// build output string
std: :ostringstream oss;
oss.fill('0');
// convert absolute time to time_t seconds
// and convert to "date time"
oss << date_time(system_clock::to_time_t(now));
oss << '. ' << setw(3) << ms.count();
return oss.str();
}
int main(a)
{
std: :cout << stamp() << '\n';
}
Copy the codeTest with a linked list of 9999 elements
The Continue version
It took nearly 39 seconds
The best version above
Take 3 ms?????? The gap is a bit big, a bit confusing
conclusion
- Continue seems to take a lot more time, not only in LeetCode, but also in native testing (although there may be errors in native testing). However, there is no specific data on the Internet to support this, I hope there is a friend who knows about this aspect can communicate with each other.
Pay attention to
Initialize the precursor to the first element!!!!
Jump out in advance, from front to back to find the position after you can jump out!!
Clever use of virtual head
LeetCode sometimes gives us lists with no head nodes, so we can construct a virtual head node ourselves!
Write in the last
- There’s a lot more to this chapter on sorting, and we’ll update hill sort, quicksort, merge sort, and more!
Finally, it was found that the average time to solve the official problem was only 10ms, which was very direct.