如何使插入排序与日期一起工作？

huangapple
go评论116阅读模式
英文:

How to get insertion sort to work with dates?

问题

对于一个关于算法的作业，我正在尝试使用插入排序对一个节点内存地址的数组进行排序。它似乎部分工作了。

  1. type bookingInfoNode struct {
  2. 	car         string
  3. 	date        string
  4. 	bookingTime int
  5. 	userName    string
  6. 	pickUp      string
  7. 	dropOff     string
  8. 	contactInfo int
  9. 	remarks     string
  10. 	bookingId   string
  11. 	prev        *bookingInfoNode
  12. 	next        *bookingInfoNode
  13. }
  15. func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
  16. 	for i := 1; i < n; i++ {
  17. 		data := arr[i]
  18. 		last := i
  19. 		dataDate, _:= time.Parse("02/01/2006", data.date)
  20. 		lastDate, _:= time.Parse("02/01/2006", arr[last-1].date)
  21. 		for (last>0) && (lastDate.After(dataDate)) {
  22. 			arr[last] = arr[last-1]
  23. 			last--
  24. 		}
  25. 		arr[last] = data
  26. 	}
  27. 	return arr
  28. }
英文:

For an assignment on algorithms, I'm trying to sort an array of node memory addresses using insertion sort. It seems to partially work?

  1. type bookingInfoNode struct {
  2. 	car         string
  3. 	date        string
  4. 	bookingTime int
  5. 	userName    string
  6. 	pickUp      string
  7. 	dropOff     string
  8. 	contactInfo int
  9. 	remarks     string
  10. 	bookingId   string
  11. 	prev        *bookingInfoNode
  12. 	next        *bookingInfoNode
  13. }
  15. func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
  16. 	for i := 1; i &lt; n; i++ {
  17. 		data := arr[i]
  18. 		last := i
  19. 		dataDate, _:= time.Parse(&quot;02/01/2006&quot;, data.date)
  20. 		lastDate, _:= time.Parse(&quot;02/01/2006&quot;, arr[last-1].date)
  21. 		for (last&gt;0) &amp;&amp; (lastDate.After(dataDate)) {
  22. 			arr[last] = arr[last-1]
  23. 			last--
  24. 		}
  25. 		arr[last] = data
  26. 	}
  27. 	return arr
  28. }

答案1

得分: 1

在大多数情况下，无论是哪种语言，除非你有一个特定的用例，需要一个特定的实现来提高性能（时间/空间方面），否则你不需要自己编写排序算法。

Go标准库中包含一个sort.Slice函数，可以帮助你对任意切片进行排序。它在内部实现了快速排序。

你的代码片段可以重写如下：

  1. func sortBookingsByDate(arr []*bookingInfoNode) []*bookingInfoNode {
  2.     sort.Slice(arr, func(i, j int) bool {
  3.         a, _ := time.Parse("02/01/2006", arr[i].date)
  4.         b, _ := time.Parse("02/01/2006", arr[j].date)
  5.         return a.Before(b)
  6.     }
  7.     return arr
  8. }

为了节省CPU周期，你还可以将time.Parse的输出缓存到一个map[*bookingInfoNode]time.Time映射中，这样你只需要解析每个日期字符串一次。你也可以在排序之前预先解析它们。

英文:

In most cases, and in most languages, you don't have to code sorting algorithms yourself unless you have a use case where a specific implementation might bring you better performances (time/space-wise)

The Go standard library contains a sort.Slice function to help you sort arbitrary slices. It implements quicksort under the hood.

Your code snippet could then be rewritten as such:

  1. func sortBookingsByDate(arr []*bookingInfoNode) []*bookingInfoNode {
  2.     sort.Slice(arr, func(i, j int) bool {
  3.         a, _ := time.Parse(&quot;02/01/2006&quot;, arr[i].date)
  4.         b, _ := time.Parse(&quot;02/01/2006&quot;, arr[j].date)
  5.         return a.Before(b)
  6.     }
  7.     return arr
  8. }

To save CPU cycles, you could also cache the time.Parse outputs into a map[*bookingInfoNode]time.Time map. So you only ever parse each date string once. You could also pre-parse it ahead of the sort.

答案2

得分: 0

经过一些调试，我意识到我的lastDate变量在内部for循环的每次迭代中没有更新。所以我将它放在了内部for循环的条件语句中，并创建了一个包装函数来解决time.Parse的错误。

  1. func getTimeFromParse(d time.Time, _ error) time.Time {
  2. 	return d
  3. }
  5. func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
  6. 	for i := 1; i < n; i++ {
  7. 		data := arr[i]
  8. 		last := i
  9. 		dataDate, _ := time.Parse(timeFormat, data.date)
  10. 		for (last > 0) && (getTimeFromParse(time.Parse(timeFormat, arr[last-1].date)).After(dataDate)) {
  11. 			arr[last] = arr[last-1]
  12. 			last--
  13. 		}
  15. 		arr[last] = data
  16. 	}
  17. 	return arr
  18. }
英文:

After some debugging, I realized that my lastDate variable was not updating with every iteration of the inner for loop. So I placed it as one of my conditionals in my inner for loop and created a wrapper function to get rid of the error from time.Parse

  1. func getTimeFromParse(d time.Time, _ error) time.Time {
  2. 	return d
  3. }
  5. func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
  6. 	for i := 1; i &lt; n; i++ {
  7. 		data := arr[i]
  8. 		last := i
  9. 		dataDate, _ := time.Parse(timeFormat, data.date)
  10. 		for (last &gt; 0) &amp;&amp; (getTimeFromParse(time.Parse(timeFormat, arr[last-1].date)).After(dataDate)) {
  11. 			arr[last] = arr[last-1]
  12. 			last--
  13. 		}
  15. 		arr[last] = data
  16. 	}
  17. 	return arr
  18. }

huangapple
  • 本文由 发表于 2022年4月19日 19:11:38
  • 转载请务必保留本文链接：https://go.coder-hub.com/71923999.html
  • go
  • insertion-sort
  • sorting
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定